The SCEAS System
Navigation Menu

Conferences in DBLP

Annual Symposium on Foundations of Computer Science (FOCS) (focs)
2009 (conf/focs/2009)


  1. Approximation Algorithms for Multicommodity-Type Problems with Guarantees Independent of the Graph Size. [Citation Graph (, )][DBLP]


  2. Faster Generation of Random Spanning Trees. [Citation Graph (, )][DBLP]


  3. Local Graph Partitions for Approximation and Testing. [Citation Graph (, )][DBLP]


  4. Oblivious Routing for the Lp-norm. [Citation Graph (, )][DBLP]


  5. Linear Systems over Composite Moduli. [Citation Graph (, )][DBLP]


  6. Multiparty Communication Complexity and Threshold Circuit Size of AC^0. [Citation Graph (, )][DBLP]


  7. The Communication Complexity of Set-Disjointness with Small Sets and 0-1 Intersection. [Citation Graph (, )][DBLP]


  8. Polynomial Hierarchy, Betti Numbers and a Real Analogue of Toda's Theorem. [Citation Graph (, )][DBLP]


  9. Randomized Self-Assembly for Exact Shapes. [Citation Graph (, )][DBLP]


  10. The Quantum and Classical Complexity of Translationally Invariant Tiling and Hamiltonian Problems. [Citation Graph (, )][DBLP]


  11. On Allocating Goods to Maximize Fairness. [Citation Graph (, )][DBLP]


  12. Online Stochastic Matching: Beating 1-1/e. [Citation Graph (, )][DBLP]


  13. Instance-Optimal Geometric Algorithms. [Citation Graph (, )][DBLP]


  14. Delaunay Triangulations in O(sort(n)) Time and More. [Citation Graph (, )][DBLP]


  15. Orthogonal Range Reporting in Three and Higher Dimensions. [Citation Graph (, )][DBLP]


  16. Decomposing Coverings and the Planar Sensor Cover Problem. [Citation Graph (, )][DBLP]


  17. Bounded Independence Fools Halfspaces. [Citation Graph (, )][DBLP]


  18. Extensions to the Method of Multiplicities, with Applications to Kakeya Sets and Mergers. [Citation Graph (, )][DBLP]


  19. Constructing Small-Bias Sets from Algebraic-Geometric Codes. [Citation Graph (, )][DBLP]


  20. Blackbox Polynomial Identity Testing for Depth 3 Circuits. [Citation Graph (, )][DBLP]


  21. A New Probability Inequality Using Typical Moments and Concentration Results. [Citation Graph (, )][DBLP]


  22. A Probabilistic Inequality with Applications to Threshold Direct-Product Theorems. [Citation Graph (, )][DBLP]


  23. Choice-Memory Tradeoff in Allocations. [Citation Graph (, )][DBLP]


  24. A Parallel Repetition Theorem for Any Interactive Argument. [Citation Graph (, )][DBLP]


  25. Resolving the Simultaneous Resettability Conjecture and a New Non-Black-Box Simulation Strategy. [Citation Graph (, )][DBLP]


  26. Extracting Correlations. [Citation Graph (, )][DBLP]


  27. Settling the Complexity of Arrow-Debreu Equilibria in Markets with Additively Separable Utilities. [Citation Graph (, )][DBLP]


  28. Reducibility among Fractional Stability Problems. [Citation Graph (, )][DBLP]


  29. Convergence of Local Dynamics to Balanced Outcomes in Exchange Networks. [Citation Graph (, )][DBLP]


  30. Convergence to Equilibrium in Local Interaction Games. [Citation Graph (, )][DBLP]


  31. Exact and Approximate Pattern Matching in the Streaming Model. [Citation Graph (, )][DBLP]


  32. Efficient Sketches for Earth-Mover Distance, with Applications. [Citation Graph (, )][DBLP]


  33. Models for the Compressible Web. [Citation Graph (, )][DBLP]


  34. The Intersection of Two Halfspaces Has High Threshold Degree. [Citation Graph (, )][DBLP]


  35. Breaking the Multicommodity Flow Barrier for O(vlog n)-Approximations to Sparsest Cut. [Citation Graph (, )][DBLP]


  36. A Complete Characterization of Statistical Query Learning with Applications to Evolvability. [Citation Graph (, )][DBLP]


  37. Agnostic Learning of Monomials by Halfspaces Is Hard. [Citation Graph (, )][DBLP]


  38. Learning and Smoothed Analysis. [Citation Graph (, )][DBLP]


  39. k-Means Has Polynomial Smoothed Complexity. [Citation Graph (, )][DBLP]


  40. Approximating Minimum Cost Connectivity Problems via Uncrossable Bifamilies and Spider-Cover Decompositions. [Citation Graph (, )][DBLP]


  41. Improved Approximation Algorithms for PRIZE-COLLECTING STEINER TREE and TSP. [Citation Graph (, )][DBLP]


  42. An O(k^3 log n)-Approximation Algorithm for Vertex-Connectivity Survivable Network Design. [Citation Graph (, )][DBLP]


  43. An Oblivious O(1)-Approximation for Single Source Buy-at-Bulk. [Citation Graph (, )][DBLP]


  44. Optimal Long Code Test with One Free Bit. [Citation Graph (, )][DBLP]


  45. Combinatorial PCPs with Efficient Verifiers. [Citation Graph (, )][DBLP]


  46. Composition of Low-Error 2-Query PCPs Using Decodable PCPs. [Citation Graph (, )][DBLP]


  47. The Complexity of Rationalizing Network Formation. [Citation Graph (, )][DBLP]


  48. Dynamic and Non-uniform Pricing Strategies for Revenue Maximization. [Citation Graph (, )][DBLP]


  49. On the Power of Randomization in Algorithmic Mechanism Design. [Citation Graph (, )][DBLP]


  50. Universal Blind Quantum Computation. [Citation Graph (, )][DBLP]


  51. Optimal Quantum Strong Coin Flipping. [Citation Graph (, )][DBLP]


  52. Two-Message Quantum Interactive Proofs Are in PSPACE. [Citation Graph (, )][DBLP]


  53. Span Programs and Quantum Query Complexity: The General Adversary Bound Is Nearly Tight for Every Boolean Function. [Citation Graph (, )][DBLP]


  54. A (log n)Omega(1) Integrality Gap for the Sparsest Cut SDP. [Citation Graph (, )][DBLP]


  55. SDP Integrality Gaps with Local ell_1-Embeddability. [Citation Graph (, )][DBLP]


  56. Integrality Gaps for Strong SDP Relaxations of UNIQUE GAMES. [Citation Graph (, )][DBLP]


  57. How to Round Any CSP. [Citation Graph (, )][DBLP]


  58. Constraint Satisfaction Problems of Bounded Width. [Citation Graph (, )][DBLP]


  59. Bit Encryption Is Complete. [Citation Graph (, )][DBLP]


  60. 2-Source Extractors under Computational Assumptions and Cryptography with Defective Randomness. [Citation Graph (, )][DBLP]


  61. (Meta) Kernelization. [Citation Graph (, )][DBLP]


  62. Planarity Allowing Few Error Vertices in Linear Time. [Citation Graph (, )][DBLP]


  63. Symmetry and Approximability of Submodular Maximization Problems. [Citation Graph (, )][DBLP]


  64. Submodular Function Minimization under Covering Constraints. [Citation Graph (, )][DBLP]


  65. Smoothed Analysis of Multiobjective Optimization. [Citation Graph (, )][DBLP]


  66. Fully Dynamic (2 + epsilon) Approximate All-Pairs Shortest Paths with Fast Query and Close to Linear Update Time. [Citation Graph (, )][DBLP]


  67. Distance Oracles for Sparse Graphs. [Citation Graph (, )][DBLP]


  68. Space-Efficient Framework for Top-k String Retrieval Problems. [Citation Graph (, )][DBLP]


  69. KKL, Kruskal-Katona, and Monotone Nets. [Citation Graph (, )][DBLP]


  70. Higher Eigenvalues of Graphs. [Citation Graph (, )][DBLP]


  71. Regularity Lemmas and Combinatorial Algorithms. [Citation Graph (, )][DBLP]


  72. Approximability of Combinatorial Problems with Multi-agent Submodular Cost Functions. [Citation Graph (, )][DBLP]


  73. The Data Stream Space Complexity of Cascaded Norms. [Citation Graph (, )][DBLP]

NOTICE1
System may not be available sometimes or not working properly, since it is still in development with continuous upgrades
NOTICE2
The rankings that are presented on this page should NOT be considered as formal since the citation info is incomplete in DBLP
 
System created by asidirop@csd.auth.gr [http://users.auth.gr/~asidirop/] © 2002
for Data Engineering Laboratory, Department of Informatics, Aristotle University © 2002