default search action
Google
Google Scholar
Semantic Scholar
Internet Archive Scholar
CiteSeerX
ORCID50th FOCS 2009: Atlanta, Georgia, USA
- 50th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2009, Atlanta, Georgia, USA, October 25-27, 2009. IEEE Computer Society 2009, ISBN 978-0-7695-3850-1
- Ankur Moitra:
Approximation Algorithms for Multicommodity-Type Problems with Guarantees Independent of the Graph Size. 3-12 - Jonathan A. Kelner, Aleksander Madry:
Faster Generation of Random Spanning Trees. 13-21 - Avinatan Hassidim, Jonathan A. Kelner, Huy N. Nguyen, Krzysztof Onak:
Local Graph Partitions for Approximation and Testing. 22-31 - Matthias Englert, Harald Räcke:
Oblivious Routing for the Lp-norm. 32-40 - Arkadev Chattopadhyay, Avi Wigderson:
Linear Systems over Composite Moduli. 43-52 - Paul Beame
, Dang-Trinh Huynh-Ngoc:
Multiparty Communication Complexity and Threshold Circuit Size of AC^0. 53-62 - Eyal Kushilevitz, Enav Weinreb:
The Communication Complexity of Set-Disjointness with Small Sets and 0-1 Intersection. 63-72 - Saugata Basu, Thierry Zell:
Polynomial Hierarchy, Betti Numbers and a Real Analogue of Toda's Theorem. 73-82 - David Doty:
Randomized Self-Assembly for Exact Shapes. 85-94 - Daniel Gottesman, Sandy Irani:
The Quantum and Classical Complexity of Translationally Invariant Tiling and Hamiltonian Problems. 95-104 - Deeparnab Chakrabarty, Julia Chuzhoy, Sanjeev Khanna:
On Allocating Goods to Maximize Fairness. 107-116 - Jon Feldman, Aranyak Mehta, Vahab S. Mirrokni, S. Muthukrishnan:
Online Stochastic Matching: Beating 1-1/e. 117-126 - Peyman Afshani, Jérémy Barbay, Timothy M. Chan:
Instance-Optimal Geometric Algorithms. 129-138 - Kevin Buchin, Wolfgang Mulzer:
Delaunay Triangulations in O(sort(n)) Time and More. 139-148 - Peyman Afshani, Lars Arge, Kasper Dalgaard Larsen:
Orthogonal Range Reporting in Three and Higher Dimensions. 149-158 - Matt Gibson, Kasturi R. Varadarajan:
Decomposing Coverings and the Planar Sensor Cover Problem. 159-168 - Ilias Diakonikolas, Parikshit Gopalan, Ragesh Jaiswal, Rocco A. Servedio, Emanuele Viola:
Bounded Independence Fools Halfspaces. 171-180 - Zeev Dvir, Swastik Kopparty, Shubhangi Saraf, Madhu Sudan:
Extensions to the Method of Multiplicities, with Applications to Kakeya Sets and Mergers. 181-190 - Avraham Ben-Aroya, Amnon Ta-Shma:
Constructing Small-Bias Sets from Algebraic-Geometric Codes. 191-197 - Neeraj Kayal, Shubhangi Saraf:
Blackbox Polynomial Identity Testing for Depth 3 Circuits. 198-207 - Ravindran Kannan:
A New Probability Inequality Using Typical Moments and Concentration Results. 211-220 - Falk Unger:
A Probabilistic Inequality with Applications to Threshold Direct-Product Theorems. 221-229 - Noga Alon, Eyal Lubetzky, Ori Gurel-Gurevich:
Choice-Memory Tradeoff in Allocations. 230-238 - Iftach Haitner:
A Parallel Repetition Theorem for Any Interactive Argument. 241-250 - Yi Deng, Vipul Goyal, Amit Sahai:
Resolving the Simultaneous Resettability Conjecture and a New Non-Black-Box Simulation Strategy. 251-260 - Yuval Ishai, Eyal Kushilevitz, Rafail Ostrovsky, Amit Sahai:
Extracting Correlations. 261-270 - Xi Chen, Decheng Dai, Ye Du, Shang-Hua Teng:
Settling the Complexity of Arrow-Debreu Equilibria in Markets with Additively Separable Utilities. 273-282 - Shiva Kintali, Laura J. Poplawski, Rajmohan Rajaraman, Ravi Sundaram, Shang-Hua Teng:
Reducibility among Fractional Stability Problems. 283-292 - Yossi Azar, Benjamin E. Birnbaum, L. Elisa Celis, Nikhil R. Devanur, Yuval Peres:
Convergence of Local Dynamics to Balanced Outcomes in Exchange Networks. 293-302 - Andrea Montanari, Amin Saberi:
Convergence to Equilibrium in Local Interaction Games. 303-312 - Benny Porat, Ely Porat:
Exact and Approximate Pattern Matching in the Streaming Model. 315-323 - Alexandr Andoni, Khanh Do Ba, Piotr Indyk, David P. Woodruff:
Efficient Sketches for Earth-Mover Distance, with Applications. 324-330 - Flavio Chierichetti, Ravi Kumar, Silvio Lattanzi, Alessandro Panconesi, Prabhakar Raghavan:
Models for the Compressible Web. 331-340 - Alexander A. Sherstov:
The Intersection of Two Halfspaces Has High Threshold Degree. 343-362 - Jonah Sherman:
Breaking the Multicommodity Flow Barrier for O(vlog n)-Approximations to Sparsest Cut. 363-372 - Vitaly Feldman:
A Complete Characterization of Statistical Query Learning with Applications to Evolvability. 375-384 - Vitaly Feldman, Venkatesan Guruswami, Prasad Raghavendra, Yi Wu:
Agnostic Learning of Monomials by Halfspaces Is Hard. 385-394 - Adam Tauman Kalai, Alex Samorodnitsky, Shang-Hua Teng:
Learning and Smoothed Analysis. 395-404 - David Arthur, Bodo Manthey, Heiko Röglin:
k-Means Has Polynomial Smoothed Complexity. 405-414 - Zeev Nutov:
Approximating Minimum Cost Connectivity Problems via Uncrossable Bifamilies and Spider-Cover Decompositions. 417-426 - Aaron Archer, MohammadHossein Bateni, Mohammad Taghi Hajiaghayi, Howard J. Karloff:
Improved Approximation Algorithms for PRIZE-COLLECTING STEINER TREE and TSP. 427-436 - Julia Chuzhoy, Sanjeev Khanna:
An O(k^3 log n)-Approximation Algorithm for Vertex-Connectivity Survivable Network Design. 437-441 - Ashish Goel, Ian Post:
An Oblivious O(1)-Approximation for Single Source Buy-at-Bulk. 442-450 - Nikhil Bansal, Subhash Khot:
Optimal Long Code Test with One Free Bit. 453-462 - Or Meir:
Combinatorial PCPs with Efficient Verifiers. 463-471 - Irit Dinur, Prahladh Harsha:
Composition of Low-Error 2-Query PCPs Using Decodable PCPs. 472-481 - Shankar Kalyanaraman, Christopher Umans:
The Complexity of Rationalizing Network Formation. 485-494 - Tanmoy Chakraborty, Zhiyi Huang, Sanjeev Khanna:
Dynamic and Non-uniform Pricing Strategies for Revenue Maximization. 495-504 - Shahar Dobzinski, Shaddin Dughmi:
On the Power of Randomization in Algorithmic Mechanism Design. 505-514 - Anne Broadbent, Joseph F. Fitzsimons, Elham Kashefi:
Universal Blind Quantum Computation. 517-526 - André Chailloux, Iordanis Kerenidis:
Optimal Quantum Strong Coin Flipping. 527-533 - Rahul Jain, Sarvagya Upadhyay, John Watrous:
Two-Message Quantum Interactive Proofs Are in PSPACE. 534-543 - Ben Reichardt:
Span Programs and Quantum Query Complexity: The General Adversary Bound Is Nearly Tight for Every Boolean Function. 544-551 - Jeff Cheeger, Bruce Kleiner, Assaf Naor:
A (log n)Omega(1) Integrality Gap for the Sparsest Cut SDP. 555-564 - Subhash Khot, Rishi Saket:
SDP Integrality Gaps with Local ell_1-Embeddability. 565-574 - Prasad Raghavendra, David Steurer:
Integrality Gaps for Strong SDP Relaxations of UNIQUE GAMES. 575-585 - Prasad Raghavendra, David Steurer:
How to Round Any CSP. 586-594 - Libor Barto, Marcin Kozik:
Constraint Satisfaction Problems of Bounded Width. 595-603 - Steven A. Myers, Abhi Shelat:
Bit Encryption Is Complete. 607-616 - Yael Tauman Kalai, Xin Li, Anup Rao:
2-Source Extractors under Computational Assumptions and Cryptography with Defective Randomness. 617-626 - Hans L. Bodlaender, Fedor V. Fomin, Daniel Lokshtanov, Eelko Penninkx, Saket Saurabh, Dimitrios M. Thilikos:
(Meta) Kernelization. 629-638 - Ken-ichi Kawarabayashi:
Planarity Allowing Few Error Vertices in Linear Time. 639-648 - Jan Vondrák:
Symmetry and Approximability of Submodular Maximization Problems. 651-670 - Satoru Iwata, Kiyohito Nagano:
Submodular Function Minimization under Covering Constraints. 671-680 - Heiko Röglin, Shang-Hua Teng:
Smoothed Analysis of Multiobjective Optimization. 681-690 - Aaron Bernstein:
Fully Dynamic (2 + epsilon) Approximate All-Pairs Shortest Paths with Fast Query and Close to Linear Update Time. 693-702 - Christian Sommer, Elad Verbin, Wei Yu:
Distance Oracles for Sparse Graphs. 703-712 - Wing-Kai Hon, Rahul Shah, Jeffrey Scott Vitter:
Space-Efficient Framework for Top-k String Retrieval Problems. 713-722 - Ryan O'Donnell, Karl Wimmer:
KKL, Kruskal-Katona, and Monotone Nets. 725-734 - Jonathan A. Kelner, James R. Lee, Gregory N. Price, Shang-Hua Teng:
Higher Eigenvalues of Graphs. 735-744 - Nikhil Bansal, Ryan Williams:
Regularity Lemmas and Combinatorial Algorithms. 745-754 - Gagan Goel, Chinmay Karande, Pushkar Tripathi, Lei Wang:
Approximability of Combinatorial Problems with Multi-agent Submodular Cost Functions. 755-764 - T. S. Jayram, David P. Woodruff:
The Data Stream Space Complexity of Cascaded Norms. 765-774
manage site settings
To protect your privacy, all features that rely on external API calls from your browser are turned off by default. You need to opt-in for them to become active. All settings here will be stored as cookies with your web browser. For more information see our F.A.Q.
last updated on 2025-12-08 09:59 CET by the dblp team
all metadata released as open data under CC0 1.0 license
see also: Terms of Use | Privacy Policy | Imprint
dblp was originally created in 1993 at:
since 2018, dblp has been operated and maintained by:
the dblp computer science bibliography is funded and supported by:
