STOC 2010 Accepted Papers (with pdf files)

STOC 2010 accepted paper list is here.
As usual (ICS 2010 pdf files, FOCS 2009 pdf files), I am collecting pointers to online versions.
  • Oblivious RAMs without Cryptographic Assumptions [ECCC]
    Miklos Ajtai (IBM Almaden Research Center)
  • 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 [arXiv]
    Alexander A. Sherstov (Microsoft Research)
  • Augmenting undirected node-connectivity by one [pdf]
    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 ([arXiv] with a different title)
    Peter Buergisser (University of Paderborn) and Felipe Cucker (City University of Hong Kong)
  • Matroid Matching: the Power of Local Search [IBM TechReport]
    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 [pdf]
    Ran Raz (Weizmann Institute)
  • Towards Polynomial Lower Bounds for Dynamic Problems [pdf]
    Mihai Patrascu (AT&T Labs)
  • Improving Exhaustive Search Implies Superpolynomial Lower Bounds [pdf]
    Ryan Williams (IBM Almaden Research Center)
  • An Optimal Ancestry Scheme and Small Universal Posets [pdf]
    Pierre Fraigniaud and Amos Korman (CNRS and Univ. Paris Diderot)
  • Tractable hypergraph properties for constraint satisfaction and conjunctive queries [arXiv]
    Dániel Marx (Tel Aviv University)
  • On the searchability of small-world networks with arbitrary underlying structure [pdf]
    Pierre Fraigniaud (CNRS and Univ. Paris Diderot) and George Giakkoupis (Univ. Paris Diderot)
  • Satisfiability Allows No Nontrivial Sparsification Unless The Polynomial-Time Hierarchy Collapses [ECCC]
    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 [arXiv]
    Raghu Meka and David Zuckerman (University of Texas at Austin)
  • How to Compress Interactive Communication [pdf]
    Boaz Barak (Princeton University), Mark Braverman (Microsoft Research New England), Xi Chen (University of Southern California) and Anup Rao (University of Washington)
  • The maximum multiflow problems with bounded fractionality [pdf]
    Hiroshi Hirai (Reseach Institute for Mathematical Sciences, Kyoto University)
  • Measuring Independence of Datasets [arXiv]
    Vladimir Braverman and Rafail Ostrovsky (UCLA)
  • On the Geometry of Differential Privacy [arXiv]
    Moritz Hardt (Princeton University) and Kunal Talwar (Microsoft Research)
  • An Invariance Principle For Polytopes [arXiv]
    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 [arXiv]
    Ashish Goel (Stanford University and Twitter), Michael Kapralov (Stanford University) and Sanjeev Khanna (University of Pennsylvania)
  • A Quantum Lovasz Local Lemma [arXiv]
    Andris Ambainis (University of Latvia), Julia Kempe (Tel Aviv University) and Or Sattath (Hebrew University and Tel Aviv University)
  • Bayesian Algorithmic Mechanism Design [arXiv]
    Jason D. Hartline (Northwestern University) and Brendan Lucier (University of Toronto)
  • A Strong Direct Product Theorem for Disjointness [arXiv]
    Hartmut Klauck (Centre for Quantum Technologies, Singapore)
  • Recognizing well-parenthesized expressions in the streaming model [arXiv]
    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 [pdf]
    Ola Svensson (KTH – Royal Institute of Technology, Stockholm)
  • An Improved LP-based Approximation for Steiner Tree [html] [pdf]
    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 [arXiv]
    Martin Dyer and David Richerby (University of Leeds)
  • Approximate Sparse Recovery: Optimizing Time and Measurements [arXiv]
    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 [arXiv]
    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 [ECCC]
    Daniele Micciancio and Panagiotis Voulgaris (UCSD)
  • Combinatorial approach to the interpolation method and scaling limits in sparse random graphs [arXiv]
    Mohsen Bayati (Stanford), David Gamarnik (MIT) and Prasad Tetali (Georgia Institute of Technology)
  • Complexity Theory for Operators in Analysis [pdf]
    Akitoshi Kawamura and Stephen Cook (University of Toronto)
  • The Median Mechanism: Interactive and Efficient Privacy with Multiple Queries [pdf]
    Aaron Roth (CMU) and Tim Roughgarden (Stanford)
  • On the Round Complexity of Covert Computation [pdf]
    Vipul Goyal (MSR India) and Abhishek Jain (UCLA)
  • Public-Key Cryptography from Different Assumptions [pdf]
    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 [arXiv]
    Venkatesan Guruswami (Carnegie Mellon University), Johan Håstad (KTH – Royal Institute of Technology) and Swastik Koppart (Massachusetts Institute of Technology)
  • Hardness Amplification in Proof Complexity [arXiv]
    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 [pdf]
    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 [abstract] [arXiv]
    Aleksander Madry (MIT)
  • Efficiency Improvements in Constructing Pseudorandom Generators from One-Way Functions [pdf]
    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 (merge of [arXiv] and [arXiv])
    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 [pdf]
    Prasad Raghavendra (Microsoft Research New England) and David Steurer (Princeton University)
  • Approximations for the Isoperimetric and Spectral Profile of Graphs and Related Parameters [pdf]
    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 [arXiv]
    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 [arXiv]
    Anindya De and Thomas Vidick (UC Berkeley)
  • On the Complexity of Circuit Satisfiability [pdf] [video]
    Ramamohan Paturi (University of California, San Diego) and Pavel Pudl\’ak (Mathematical Institute of the Czech Academy of Sciences)
  • Multi-parameter mechanism design and sequential posted pricing [arXiv]
    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 [arXiv]
    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 [pdf]
    Elad Verbin (ITCS, Tsinghua University) and Qin Zhang (Hong Kong University of Science and Technology)
  • Optimal Homologous Cycles, Total Unimodularity, and Linear Programming [arXiv]
    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 [pdf]
    Fabian Kuhn (University of Lugano), Nancy Lynch (MIT) and Rotem Oshman (MIT)
  • Maintaining a Large Matching or a Small Vertex Cover [html]
    Krzysztof Onak (MIT) and Ronitt Rubinfeld (MIT and Tel Aviv University)
  • Almost Tight Bounds for Rumour Spreading with Conductance [pdf]
    Flavio Chierichetti, Silvio Lattanzi and Alessandro Panconesi (Sapienza University)
  • Changing Base without Losing Space ([pdf] with a different title)
    Yevgeniy Dodis (New York University) and Mihai Patrascu (AT&T Labs) and Mikkel Thorup (AT&T Labs)

Logspace vs Polynomial time

One of the primary goals of complexity theory is separating complexity classes, a.k.a proving lower bounds. Embarrassingly we have only a handful of unconditional separation results. Separating P from NP is of course the mother of all such goals. Anybody who understands the philosophical underpinnings of the P vs NP problem would love to LIVE to see its resolution. Towards resolving this, we made some (“anti”)-progress (Eg : Relativization, Natural proofs, Algebrization) and have a new geometric complexity theory approach which relies on an Extended-Extended-Extended-Extended-Riemann-Hypothesis !! For more information about the history and status of P vs NP problem read Sipser’s paper [Sipser'92], Allender’s status report [Allender'09] or Fortnow’s article [Fortnow'09].

Today’s post is about the Logspace (L) vs Polynomial time (P) problem, which (in my opinion) is right next to the P vs NP problem in its theoretical importance. I guess many researchers believe that L \neq P. Did we make any progress/anti-progress towards resolving the L \neq P conjecture ?  Here are two attempts both based on branching programs and appeared in MFCS with a gap of 20 years !!

1) A conjecture by Barrington and McKenzie (BM’89): The problem GEN is defined as follows :

GEN : Given an n \times n table filled with entries from \{1,2,\dots,n\}, which we interpret as the multiplication table of an n-element groupoid, and a subset S of \{1,2,\dots,n\} which includes element 1, determine whether the subgroupoid <S>, defined as the closure of S under the groupoid product, includes element n.

Barrington-McKenzie Conjecture : For each n > 1, a branching program in which each node can only evaluate a binary product within an n-element groupoid, branching n ways according to the n possible outcomes, must have at least 2^{n-2} nodes to solve all n \times n GEN instances with singleton starting set S.

The problem GEN is known to be P-complete [JL'76]. Barrington-McKenzie Conjecture would imply that GEN \notin DSPACE({{\log}^k}n) for any k. In particular, it would imply that L \neq P. I don’t know if there is any partial progress towards resolving this conjecture.

2) Thrifty Hypothesis : This is a recent approach by Braverman et. al [BCMSW'09] towards proving a stronger theorem L \neq LogDCFL. Stephen Cook presented this approach at Valiant’s 60th birthday celebration and Barriers Workshop. He also announced a $100 prize for solving an intermediate open problem mentioned in his slides.

Tree Evaluation Problem (TEP): The input to the problem is a rooted, balanced d-ary tree of height h, whose internal nodes are labeled with d-ary functions on [k] = \{1, . . . , k\}, and whose leaves are labeled with elements of [k]. Each node obtains a value in [k] equal to its d-ary function applied to the values of its d children. The output is the value of the root.

In their paper they show that TEP \in LogDCFL and conjecture that TEP \notin L. They introduce Thrifty Branching Programs and prove that TEP can be solved by a thrifty branching program. A proof of the following conjecture implies that L \neq LogDCFL. For more details, read this paper.
Thrifty Hypothesis : Thrifty Branching Programs are optimal among deterministic branching programs solving TEP.

Open Problems :

  • My knowledge about the history of L vs P problem is limited.  Are there other approaches/attempts in the last four decades to separate L from P ?
  • An intermediate open problem is mentioned in the last slide of these slides. The authors announced $100 prize for the first correct proof. Read their paper for more open problems.

References :

  • [BM'89] David A. Mix Barrington, Pierre McKenzie: Oracle Branching Programs and Logspace versus P. MFCS 1989: 370-379
  • [BCMSW'09] Mark Braverman, Stephen A. Cook, Pierre McKenzie, Rahul Santhanam, Dustin Wehr: Branching Programs for Tree Evaluation. MFCS 2009: 175-186
  • [Sipser'92] Michael Sipser: The History and Status of the P versus NP Question STOC 1992: 603-618
  • [Allender'09] Eric Allender: A Status Report on the P Versus NP Question. Advances in Computers 77: 117-147 (2009) [pdf]
  • [Fortnow'09] Lance Fortnow: The status of the P versus NP problem. Commun. ACM 52(9): 78-86 (2009) [pdf]
  • [JL'76] Neil D. Jones, William T. Laaser: Complete Problems for Deterministic Polynomial Time. Theor. Comput. Sci. 3(1): 105-117 (1976)