50. FOCS 2009:
Atlanta, Georgia, USA
50th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2009, October 25-27, 2009, Atlanta, Georgia, USA.
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 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 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

Last update Fri May 24 02:34:29 2013
CET by the DBLP Team —
Data released under the ODC-BY 1.0 license — See also our legal information page