50. FOCS 2009: Atlanta, Georgia, USA

• 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