List of Accepted Papers

Below are a list of the accepted papers to STOC 2010, including their authors. This list is preliminary and subject to change.

• Budget Constrained Auctions with Heterogeneous Items
  Sayan Bhattacharya (Duke), Gagan Goel (Georgia Tech), Sreenivas Gollapudi (Microsoft Research) and Kamesh Munagala (Duke)
• On the Structure of Cubic and Quartic Polynomials
  Elad Haramaty and Amir Shpilka (Technion)
• BQP and the Polynomial Hierarchy
  Scott Aaronson (MIT)
• Sorting under Partial Information (without the Ellipsoid Algorithm)
  Jean Cardinal (ULB), Samuel Fiorini (ULB), Gwenaël Joret (ULB), Raphaël Jungers (MIT) and J. Ian Munro (University of Waterloo)
• Approximation Schemes for Steiner Forest on Planar Graphs and Graphs of Bounded Treewidth
  MohammadHossein Bateni (Princeton University), MohammadTaghi Hajiaghayi (AT&T Labs -- Research) and Dániel Marx (Tel Aviv University)
• Extensions and Limits to Vertex Sparsification
  Tom Leighton (MIT and Akamai Technologies, Inc) and Ankur Moitra (MIT)
• Efficiently Learning Mixtures of Two Gaussians
  Adam Tauman Kalai (Microsoft), Ankur Moitra (MIT), and Gregory Valiant (UC Berkeley)
• Oblivious RAMs without Cryptographic Assumptions
  Miklos Ajtai (IBM Almaden Research Center)
• The HOM problem is decidable
  Guillem Godoy, Omer Giménez, Lander Ramos and Carme Àlvarez (Universitat Polit`ecnica de Catalunya)
• Deterministic identity testing of depth-4 multilinear circuits with bounded top fan-in
  Zohar S. Karnin and Partha Mukhopadhyay and Amir Shpilka and Ilya Volkovich (Technion)
• Improved Algorithms for Computing Fisher's Market Clearing Prices
  James B. Orlin (MIT)
• Optimal Bounds for Sign-Representing the Intersection of Two Halfspaces by Polynomials
  Alexander A. Sherstov (Microsoft Research)
• QIP = PSPACE
  Rahul Jain (National University of Singapore), Zhengfeng Ji (Perimeter Institute), Sarvagya Upadhyay (University of Waterloo) and John Watrous (University of Waterloo)
• Augmenting undirected node-connectivity by one
  Laszlo A. Vegh (MTA-ELTE Egervary Research Group and Department of Operations Research, Eotvos University)
• Solving Polynomial Equations in Smoothed Polynomial Time and a Near Solution to Smale's 17th Problem
  Peter Buergisser (University of Paderborn) and Felipe Cucker (City University of Hong Kong)
• Matroid Matching: the Power of Local Search
  Jon Lee (IBM TJ Watson Research Center), Maxim Sviridenko (IBM TJ Watson Research Center) and Jan Vondrak (IBM Almaden Research Center)
• Tensor-Rank and Lower Bounds for Arithmetic Formulas
  Ran Raz (Weizmann Institute)
• Towards Polynomial Lower Bounds for Dynamic Problems
  Mihai Patrascu (AT&T Labs)
• Improving Exhaustive Search Implies Superpolynomial Lower Bounds
  Ryan Williams (IBM Almaden Research Center)
• An Optimal Ancestry Scheme and Small Universal Posets
  Pierre Fraigniaud and Amos Korman (CNRS and Univ. Paris Diderot)
• Tractable hypergraph properties for constraint satisfaction and conjunctive queries
  Dániel Marx (Tel Aviv University)
• On the searchability of small-world networks with arbitrary underlying structure
  Pierre Fraigniaud (CNRS and Univ. Paris Diderot) and George Giakkoupis (Univ. Paris Diderot)
• Satisfiability Allows No Nontrivial Sparsification Unless The Polynomial-Time Hierarchy Collapses
  Holger Dell (Humboldt University of Berlin) and Dieter van Melkebeek (University of Wisconsin-Madison)
• A shorter proof of the Graph Minor Algorithm - The Unique Linkage Theorem -
  Ken-ichi Kawarabayashi (National Institute of Informatics, Tokyo) and Paul Wollan (University of Rome, La Sapienza)
• Pseudorandom Generators for Polynomial Threshold Functions
  Raghu Meka and David Zuckerman (University of Texas at Austin)
• How to Compress Interactive Communication
  Boaz Barak (Princeton University), Mark Braverman (Microsoft Research New England), Xi Chen (University of Southern California) and Anup Rao (University of Washington)
• Zero-One Frequency Laws
  Vladimir Braverman and Rafail Ostrovsky (UCLA)
• The maximum multiflow problems with bounded fractionality
  Hiroshi Hirai (Reseach Institute for Mathematical Sciences, Kyoto University)
• Measuring Independence of Datasets
  Vladimir Braverman and Rafail Ostrovsky (UCLA)
• On the Geometry of Differential Privacy
  Moritz Hardt (Princeton University) and Kunal Talwar (Microsoft Research)
• An Invariance Principle For Polytopes
  Prahladh Harsha (Tata Institute of Fundamental Research), Adam Klivans (UT-Austin) and Raghu Meka (UT-Austin)
• Perfect Matchings in O(n log n) Time in Regular Bipartite Graphs
  Ashish Goel (Stanford University and Twitter), Michael Kapralov (Stanford University) and Sanjeev Khanna (University of Pennsylvania)
• A Quantum Lovasz Local Lemma
  Andris Ambainis (University of Latvia), Julia Kempe (Tel Aviv University) and Or Sattath (Hebrew University and Tel Aviv University)
• Bayesian Algorithmic Mechanism Design
  Jason D. Hartline (Northwestern University) and Brendan Lucier (University of Toronto)
• A Strong Direct Product Theorem for Disjointness
  Hartmut Klauck (Centre for Quantum Technologies, Singapore)
• Recognizing well-parenthesized expressions in the streaming model
  Frederic Magniez (LRI, Univ. Paris-Sud, CNRS), Claire Mathieu (Brown University) and Ashwin Nayak (U. Waterloo and Perimeter Institute)
• Conditional Hardness of Precedence Constrained Scheduling on Identical Machines
  Ola Svensson (KTH - Royal Institute of Technology, Stockholm)
• An Improved LP-based Approximation for Steiner Tree
  Jaroslaw Byrka (EPFL, Lausanne), Fabrizio Grandoni (Universita di Roma Tor Vergata), Thomas Rothvoss (EPFL, Lausanne) and Laura Sanita (EPFL, Lausanne)
• On the Complexity of #CSP
  Martin Dyer and David Richerby (University of Leeds)
• Approximate Sparse Recovery: Optimizing Time and Measurements
  Anna Gilbert (University of Michigan) Yi Li (University of Michigan), Ely Porat (Bar Ilan University) and Martin Strauss (University of Michigan)
• On the Hardness of the Noncommutative Determinant
  Vikraman Arvind and Srikanth Srinivasan (Institute of Mathematical Sciences, Chennai)
• A Deterministic Single Exponential Time Algorithm for Most Lattice Problems based on Voronoi Cell Computations
  Daniele Micciancio and Panagiotis Voulgaris (UCSD)
• Combinatorial approach to the interpolation method and scaling limits in sparse random graphs
  Mohsen Bayati (Stanford), David Gamarnik (MIT) and Prasad Tetali (Georgia Institute of Technology)
• Weighted Geometric Set Cover via Quasi-Uniform Sampling
  Kasturi Varadarajan (University of Iowa)
• Complexity Theory for Operators in Analysis
  Akitoshi Kawamura and Stephen Cook (University of Toronto)
• Odd Cycle Packing
  Ken-ichi Kawarabayashi (National Institute of Informatics, Japan) and Bruce Reed (McGill University and Projet MASCOTTE)
• The Median Mechanism: Interactive and Efficient Privacy with Multiple Queries
  Aaron Roth (CMU) and Tim Roughgarden (Stanford)
• On the Round Complexity of Covert Computation
  Vipul Goyal (MSR India) and Abhishek Jain (UCLA)
• Public-Key Cryptography from Different Assumptions
  Benny Applebaum (Weizmann Institute of Science), Boaz Barak (Princeton University) and Avi Wigderson (Institute for Advanced Study)
• On the List-Decodability of Random Linear Codes
  Venkatesan Guruswami (Carnegie Mellon University), Johan Håstad (KTH - Royal Institute of Technology) and Swastik Kopparty (Massachusetts Institute of Technology)
• Hardness Amplification in Proof Complexity
  Paul Beame (University of Washington), Trinh Huynh (University of Washington) and Toniann Pitassi (University of Toronto)
• Non-commutative circuits and the sum-of-squares problem
  Pavel Hrubes (Princeton University), Avi Wigderson (Institute for Advanced Study) and Amir Yehudayoff (Institute for Advanced Study)
• Faster approximation schemes for fractional multicommodity flow problems via dynamic graph algorithms
  Aleksander Madry (MIT)
• Efficiency Improvements in Constructing Pseudorandom Generators from One-Way Functions
  Iftach Haitner (Microsoft Research New England), Omer Reingold (Microsoft Research Silicon Valley and Weizmann Institute of Science) and Salil Vadhan (Harvard University)
• Load balancing and orientability thresholds for random hypergraphs
  Pu Gao and Nicholas Wormald (University of Waterloo)
• Bounding the average sensitivity and noise sensitivity of polynomial threshold functions
  Ilias Diakonikolas (Columbia University), Prahladh Harsha (Tata Institute of Fundamental Research), Adam R. Klivans (University of Texas), Raghu Meka (University of Texas), Prasad Raghavendra (Microsoft Research New England), Rocco A. Servedio (Columbia University) and Li-Yang Tan (Columbia University)
• Graph Expansion and the Unique Games Conjecture
  Prasad Raghavendra (Microsoft Research New England) and David Steurer (Princeton University)
• Approximations for the Isoperimetric and Spectral Profile of Graphs and Related Parameters
  Prasad Raghavendra (Microsoft Research New England), David Steurer (Princeton University) and Prasad Tetali (Georgia Tech)
• Detecting High Log-Densities -- an $O(n^{1/4})$ Approximation for Densest $k$-Subgraph
  Aditya Bhaskara (Princeton University), Moses Charikar (Princeton University), Eden Chlamtac (Weizmann Institute of Science), Uriel Feige (Weizmann Institute of Science) and Aravindan Vijayaraghavan (Princeton University)
• Near-optimal extractors against quantum storage
  Anindya De and Thomas Vidick (UC Berkeley)
• On the Complexity of Circuit Satisfiability
  Ramamohan Paturi (University of California, San Diego) and Pavel Pudl\'ak (Mathematical Institute of the Czech Academy of Sciences)
• Connectivity Oracles for Failure Prone Graphs
  Seth Pettie and Ran Duan (University of Michigan)
• Multi-parameter mechanism design and sequential posted pricing
  Shuchi Chawla (University of Wisconsin-Madison), Jason Hartline (Northwestern University), David Malec (University of Wisconsin-Madison) and Balasubramanian Sivan (University of Wisconsin-Madison)
• Subgraph Sparsification and Nearly Optimal Ultrasparsifiers
  Alexandra Kolla (Institute for Advanced Study), Yury Makarychev (Toyota Technological Institute at Chicago), Amin Saberi (Stanford University) and Shang-Hua Teng (University of Southern California)
• Bilipschitz snowflakes, metrics of negative type, and PSD flows
  James R. Lee and Mohammad Moharrami (University of Washington)
• The Limits of Buffering: A Tight Lower Bound for Dynamic Membership in the External Memory Model
  Elad Verbin (ITCS, Tsinghua University) and Qin Zhang (Hong Kong University of Science and Technology)
• Optimal Homologous Cycles, Total Unimodularity, and Linear Programming
  Tamal K. Dey (Ohio State University), Anil N. Hirani (University of Illinois at Urbana-Champaign) and Bala Krishnamoorthy (Washington State University)
• Distributed Computation in Dynamic Networks
  Fabian Kuhn (University of Lugano), Nancy Lynch (MIT) and Rotem Oshman (MIT)
• A Full Characterization of Quantum Advice
  Scott Aaronson and Andrew Drucker (MIT)
• Maintaining a Large Matching or a Small Vertex Cover
  Krzysztof Onak (MIT) and Ronitt Rubinfeld (MIT and Tel Aviv University)
• Almost Tight Bounds for Rumour Spreading with Conductance
  Flavio Chierichetti, Silvio Lattanzi and Alessandro Panconesi (Sapienza University)
• Changing Base without Losing Space
  Yevgeniy Dodis (New York University) and Mihai Pastrascu (AT&T Labs) and Mikkel Thorup (AT&T Labs)
• The Price of Privately Releasing Contingency Tables and the Spectra of Random Matrices with Correlated Rows
  Shiva Kasiviswanathan (Los Alamos National Laboratory), Mark Rudelson (University of Missouri), Adam Smith (Pennsylvania State University) and Jonathan Ullman (Harvard University)
• Saving Space by Algebraization
  Daniel Lokshtanov and Jesper Nederlof (University of Bergen)
• Privacy Amplification with Asymptotically Optimal Entropy Loss
  Nishanth Chandran (UCLA), Bhavana Kanukurthi (Boston University), Rafail Ostrovsky (UCLA) and Leonid Reyzin (Boston University)
• A Sparse Johnson-Lindenstrauss Transform
  Anirban Dasgupta and Ravi Kumar and Tamas Sarlos (Yahoo! Research)
• Local List-Decoding and Testing of Random Linear Codes from High-Error
  Swastik Kopparty and Shubhangi Saraf (MIT)
• Differential Privacy Under Continual Observation
  Cynthia Dwork (Microsoft Research), Moni Naor (Weizmann Institute), Toniann Pitassi (University of Toronto) and Guy Rothblum (Princeton University)