FOCS 2009 Main Page

CFP

FAQ

Accepted Papers

program

FOCS 2009 Program

Saturday, Oct 24

Celebration of 50th FOCS and 20th Anniversary of ACO at Georgia Tech


Saturday, Oct 24


Reception 7:00-9:00, Renaissance Hotel Ballroom


Sunday, Oct 25

Session 1A 9:00 - 10:40 (Chair: Phil Klein)

  • Approximation Algorithms for Multicommodity-Type Problems with Guarantees Independent of the Graph Size
    Ankur Moitra.
  •  Faster generation of random spanning trees
    Jonathan Kelner and Aleksander Madry.
  • Local Graph Partitions for Approximation and Testing
    Avinatan Hassidim, Jonathan Kelner, Huy Nguyen and Krzysztof Onak.
  • Oblivious Routing for the L_p-norm
    Matthias Englert and Harald Räcke.

Session 1B 9:00 - 10:40 (Chair: Mark Braverman)

  • Linear systems over composite moduli
    Arkadev Chattopadhyay and Avi Wigderson.
  • Multiparty Communication Complexity and Threshold Circuit Complexity of AC^0
    Dang-Trinh Huynh-Ngoc and Paul Beame.
  • The Communication Complexity of Set-Disjointness with Small Sets and 0-1 Intersection
    Eyal Kushilevitz and Enav Weinreb.
  • Polynomial hierarchy, Betti numbers and a real analogue of Toda's Theorem
    Saugata Basu and Thierry Zell.

Session 2A 11:10 - 12:00 (Chair: Alon Efrat)

  • Randomized Self-Assembly for Exact Shapes
    David Doty.
  • The Quantum and Classical Complexity of Translationally Invariant Tiling and Hamiltonian Problems
    Sandy Irani and Daniel Gottesman.

Session 2B 11:10 - 12:00 (Chair: Ming Li)

  • On Allocating Goods to Maximize Fairness
    Deeparnab Chakrabarty, Julia Chuzhoy and Sanjeev Khanna.
  • Online Stochastic Matching: Beating 1-1/e
    Jon Feldman, Aranyak Mehta, Vahab Mirrokni and S. Muthukrishnan.

Session 3A 1:30 - 3:10 (Chair: Ken Clarkson)

  • Instance-Optimal Geometric Algorithms
    Peyman Afshani, Jeremy Barbay and Timothy M. Chan.
  • Delaunay Triangulations in O(sort(n)) and Other Transdichotomous and Hereditary Algorithms in Computational Geometry
    Kevin Buchin and Wolfgang Mulzer.
  • Orthogonal Range Reporting in Three and Higher Dimensions
    Peyman Afshani, Lars Arge and Kasper Dalgaard Larsen.
  • Decomposing Coverings and the Planar Sensor Cover Problem
    Matt Gibson and Kasturi Varadarajan.

Session 3B 1:30 - 3:10 (Chair: Amit Chakrabarti)

  • Bounded Independence Fools Halfspaces
    Ilias Diakonikolas, Parikshit Gopalan, Ragesh Jaiswal, Rocco Servedio and Emanuele Viola.
  • Extensions to the Method of Multiplicities, with applications to Kakeya sets and Mergers
    Zeev Dvir, Swastik Kopparty, Shubhangi Saraf and Madhu Sudan.
  • Constructing Small-Bias Sets from Algebraic-Geometric Codes
    Avraham Ben-Aroya and Amnon Ta-Shma.
  • Blackbox Polynomial Identity Testing for Depth 3 Circuits
    Neeraj Kayal and Shubhangi Saraf.

Session 4A 3:40 - 4:55 (Chair: Eli Upfal)

  • A new probability inequality using typical moments and concentration results
    Ravindran Kannan.
  • A Probabilistic Inequality with Applications to Threshold Direct Product Theorems
    Falk Unger.
  • Choice-memory tradeoff in allocations
    Noga Alon, Ori Gurel-Gurevich and Eyal Lubetzky.

Session 4B 3:40 - 4:55 (Chair: Boaz Barak)

  • A Parallel Repetition Theorem for Any Interactive Argument
    Iftach Haitner.
  • Resolving the Simultaneous Resettability Conjecture and a New Non-Black-Box Simulation Strategy
    Yi Deng, Vipul Goyal and Amit Sahai.
  • Extracting Correlations
    Yuval Ishai, Eyal Kushilevitz, Rafail Ostrovsky and Amit Sahai.

Sunday, Oct 25


Business Meeting, 9:00-10:00, Renaissance Hotel Ballroom

Monday, Oct 26

Session 5A 9:00 - 10:40 (Chair: Tim Roughgarden)

  • Settling the Complexity of Arrow-Debreu Equilibria in Markets with Additively Separable Utilities
    Xi Chen, Decheng Dai, Ye Du and Shang-Hua Teng.
  • Reducibility Among Fractional Stability Problems
    Shiva Kintali, Laura Poplawski, Rajmohan Rajaraman, Ravi Sundaram and Shang-Hua Teng.
  • Convergence of Local Dynamics to Balanced Outcomes in Exchange Networks
    Yossi Azar, Benjamin Birnbaum, L. Elisa Celis, Nikhil R. Devanur and Yuval Peres.
  • Convergence to Equilibrium in Local Interaction Games
    Andrea Montanari and Amin Saberi.

Session 5B 9:00 - 10:40 (Chair: Anna Gilbert)

  • Exact And Approximate Pattern Matching In The Streaming Model
    Ely Porat and Benny Porat.
  • The Data Stream Space Complexity of Cascaded Norms
    T.S. Jayram and David Woodruff.
  • Efficient sketches for Earth-Mover Distance, with applications
    Alexandr Andoni, Khanh Do Ba, Piotr Indyk and David Woodruff.
  • Models for the compressible Web
    Flavio Chierichetti, Ravi Kumar, Silvio Lattanzi, Alessandro Panconesi and Prabhakar Raghavan.

Session 6 11:10 - 12:10 (Chair: Daniel Spielman)

  • The Intersection of Two Halfspaces Has High Threshold Degree
    Alexander Sherstov.
  • Breaking the Multicommodity Flow Barrier for O(sqrt(log n))-approximations to Sparsest Cut
    Jonah Sherman.

Session 7A 1:30 - 3:10 (Chair: Maria Florina Balcan)

  • A Complete Characterization of Statistical Query Learning with Applications to Evolvability
    Vitaly Feldman.
  • Agnostic Learning of Monomials by Halfspaces is Hard
    Vitaly Feldman, Venkatesan Guruswami, Prasad Raghavendra and Yi Wu.
  • Learning and Smoothed Analysis
    Adam Kalai, Alex Samorodnitsky and Shang-Hua Teng.
  • k-Means has Polynomial Smoothed Complexity
    David Arthur, Bodo Manthey and Heiko Roeglin.

Session 7B 1:30 - 3:10 (Chair: Vijay Vazirani)

  • Approximating minimum cost connectivity problems via uncrossable bifamilies and spider-cover decompositions
    Zeev Nutov.
  • Improved Approximation Algorithms for Prize-Collecting Steiner Tree and TSP
    Aaron Archer, MohammadHossein Bateni, MohammadTaghi Hajiaghayi and Howard Karloff.
  • An O(k^3 log n)-Approximation Algorithm for Vertex-Connectivity Survivable Network Design
    Julia Chuzhoy and Sanjeev Khanna.
  • An Oblivious O(1)-Approximation for Single Source Buy-at-Bulk
    Ashish Goel and Ian Post.

Session 8A 3:40 - 4:55 (Chair: Sanjeev Arora)

  • Optimal Long Code Test with One Free Bit
    Nikhil Bansal and Subhash Khot.
  • Combinatorial PCPs with efficient verifiers
    Or Meir.
  • Composition of low-error 2-query PCPs using decodable PCPs
    Irit Dinur and Prahladh Harsha.

Session 8B 3:40 - 4:55 (Chair: Berthold Vöcking)

  • The Complexity of Rationalizing Network Formation
    Shankar Kalyanaraman and Christopher Umans.
  • Dynamic and Non-Uniform Pricing Strategies for Revenue Maximization
    Tanmoy Chakraborty, Zhiyi Huang and Sanjeev Khanna.
  • On the Power of Randomization in Algorithmic Mechanism Design
    Shahar Dobzinski and Shaddin Dughmi.

Tuesday, Oct 27

Session 9A 9:00 - 10:40 (Chair: Umesh Vazirani)

  • Universal Blind Quantum Computation
    Anne Broadbent, Joseph Fitzsimons and Elham Kashefi.
  • Optimal quantum strong coin flipping
    André Chailloux and Iordanis Kerenidis.
  • Two-message quantum interactive proofs are in PSPACE
    Rahul Jain, Sarvagya Upadhyay and John Watrous.
  • Span programs and quantum query complexity: The general adversary bound is nearly tight for every boolean function
    Ben Reichardt.

Session 9B 9:00 - 10:40 (Chair: Kunal Talwar)

  • A $(\log n)^{\Omega(1)}$ integrality gap for the Sparsest Cut SDP
    Jeff Cheeger, Bruce Kleiner and Assaf Naor.
  • SDP Integrality Gaps with Local $\ell_1$-Embeddability
    Subhash Khot and Rishi Saket.
    Integrality gaps for Strong SDP Relaxations of Unique Games
    Prasad Raghavendra and David Steurer.
  • How to Round Any CSP
    Prasad Raghavendra and David Steurer.
  • Constraint Satisfaction Problems of Bounded Width
    Libor Barto and Marcin Kozik.

Session 10A 11:10 - 12:00 (Chair: Dana Ron)

  • One bit encryption is complete
    Steven Myers and abhi shelat.
  • 2-Source Extractors Under Computational Assumptions and Cryptography with Defective Randomness
    Yael Tauman Kalai, Xin Li and Anup Rao.

Session 10B 11:10 - 12:00 (Chair: Martin Fürer)

  • (Meta) Kernelization
    Hans Bodlaender, Fedor Fomin, Daniel Lokshtanov, Eelko Penninkx, Saket Saurabh and Dimitrios Thilikos.
  • Planarity allowing few error vertices in linear time
    Ken-ichi Kawarabayashi.

Session 11A 1:30 - 2:45 (Chair: Daniel Spielman)

  • Symmetry and approximability of submodular maximization problems
    Jan Vondrak.
  • Submodular Function Minimization under Covering Constraints
    Satoru Iwata and Kiyohito Nagano.
    Approximability of Combinatorial Problems with Multi-agent Submodular Cost Functions
    Gagan Goel, Chinmay Karande, Pushkar Tripathi and Lei Wang.
  • Smoothed Analysis of Multiobjective Optimization
    Heiko Roeglin and Shang-Hua Teng.

Session 11B 1:30 - 2:45 (Chair: Mihai Pătraşcu)

  • Fully Dynamic $(2 + \eps)$ Approximate All-Pairs Shortest Paths with $O(\log \log n)$ Query and Close to Linear Update Time
    Aaron Bernstein.
  • Distance Oracles for Sparse Graphs
    Christian Sommer, Elad Verbin and Wei Yu.
  • Space-Efficient Framework for Top-k String Retrieval Problems
    Wing Kai Hon, Rahul Shah and Jeffrey Scott Vitter.

Session 12 3:15 - 4:30 (Chair: Mario Szegedy)

  • KKL, Kruskal-Katona, and monotone nets
    Ryan O'Donnell and Karl Wimmer.
  • Higher eigenvalues of graphs
    Jonathan Kelner, James Lee, Gregory Price and Shanghua Teng.
  • Regularity Lemmas and Combinatorial Algorithms
    Nikhil Bansal and Ryan Williams.