STOC 2012 Accepted Papers (with pdf files)

STOC 2012 accepted paper list is here. Following are PDF pointers to online versions.

    • Separating multilinear branching programs and formulas [ECCC]
      Zeev Dvir, Guillaume Malod, Sylvain Perifel, Amir Yehudayoff
    • $2^{log^{1-\epsilon} n}$ Hardness for Closest Vector Problem with Preprocessing [ECCC]
      Subhash Khot, Preyas Popat, Nisheeth Vishnoi
    • Determinism versus Nondeterminism with Arithmetic Tests and Computation [ECCC]
      Miklos Ajtai
    • Short Proofs for the Determinant Identities [arXiv]
      Pavel Hrubes, Iddo Tzameret
    • The Cell Probe Complexity of Dynamic Range Counting [arXiv]
      Kasper Green Larsen
    • Subspace Evasive Sets [arXiv]
      Zeev Dvir, Shachar Lovett
    • Monotone expansion [arXiv]
      Jean Bourgain, Amir Yehudayoff
    • Solution of the propeller conjecture in $R^3$ [arXiv]
      Steven Heilman, Aukosh Jagannath, Assaf Naor
    • Linear vs. Semidefinite Extended Formulations: Exponential Separation and Strong Lower Bounds [arXiv]
      Samuel Fiorini, Serge Massar, Sebastian Pokutta, Hans Raj Tiwary, Ronald deWolf
    • On Vertex Sparsifiers with Steiner Nodes 
      Julia Chuzhoy
    • Strongly polynomial algorithm for a class of minimum-cost flow problems with separable convex objectives [arXiv]
      Laszlo A. Vegh
    • Routing in Undirected Graphs with Constant Congestion [arXiv]
      Julia Chuzoy
    • Pseudorandom Generators with Long Stretch and Low Locality from Random Local One-Way Functions [ECCC]
      Benny Applebaum
    • Catching the k-NAESAT threshold [arXiv]
      Amin Coja-Oghlan, Konstantinos Panagiotou
    • Edge Transitive Ramanujan Graphs and Highly Symmetric LDPC Good Codes [arXiv]
      Tali Kaufman, Alexander Lubotzky
    • A quantitative Gibbard-Satterthwaite theorem without neutrality [arXiv]
      Elchanan Mossel, Miklos Z. Racz
    • From Irreducible Representations to Locally Decodable Codes [arXiv]
      Kim Efremenko
    • Reconstruction of Depth-4 Multlinear circuits with Top Fan-in 2 [arXiv]
      Ankit Gupta, Neeraj Kayal, Satya Lokam
    • Approximation Algorithms and Hardness of Integral Concurrent Flow 
      Parinya Chalermsook, Julia Chuzoy, Alina Ene, Shi Li
    • Interactive Information Complexity [ECCC]
      Mark Braverman
    • Finding red balloons with split contracts: robustness to individuals’ selfishness [pdf]
      Manuel Cebrian, Lorenzo Coviello, Andrea Vattani, Panagiotis Voulgaris
    • Span Programs for Functions with Constant-Sized 1-certificates [arXiv]
      Aleksandrs Belovs
    • Time-Space Tradeoffs in Resolution: Superpolynomial Lower Bounds for Superlinear Space [ECCC]
      Paul Beame, Chris Beck, Russell Impagliazzo
    • Fast Matrix Rank Algorithms and Applications 
      Ho Yee Cheung, Tsz Chiu Kwok, Lap Chi Lau
    • Nearly Complete Graphs Decomposable into Large Induced Matchings and their Applications [arXiv]
      Noga Alon, Ankur Moitra, Benny Sudakov
    • When the Cut Condition is Enough; A Complete Characterization for Multiflow Problems in Series-Parallel Networks 
      Amit Chakrabarti, Lisa Fleisher, Christophe Weibel
    • Approximating the Exponential, the Lancoz Method and an $\tilde{O}(m)$-Time Spectral Algorithm for Balanced Separator [arXiv]
      Lorenzo Orecchia, Sushant Sachdeva, Nisheeth Vishnoi
    • Tight Bounds for Monotone Switching Networks via Fourier Analysis
      Siu Man Chan, Aaron Potechin
    • Tight Bounds for Distributed Functional Monitoring [arXiv]
      David P. Woodruff, Qin Zhang
    • Global Computation in a Poorly Connected World: Fast Rumor Spreading with No Dependence on Conductance [arXiv]
      Keren Censor-Hillel, Bernhard Haeupler, Jonathan A. Kelner, Petar Maymounkov
    • Folded Codes from Function Field Towers and Improved List Decoding 
      Venkatesan Guruswami, Chaoping Xing
    • Improved Smoothed Analysis of Multiobjective Optimization [arXiv]
      Tobias Brunsch, Heiko Roglin
    • Improving Chrisofides’ Algorithm for the s-t Path TSP [arXiv]
      Hyung-Chan An, Robert Kleinberg, David B. Shmoys
    • Probabilistic existence of rigid combinatorial structures [arXiv]
      Greg Kuperberg, Shachar Lovett, Ron Peled
    • Quantum Money from Hidden Subspaces 
      Scott Aaronson, Paul Christiano
    • A Complementary Pivot Algorithm for Market Equilibrium under Separable, Piecewise-Linear Concave Utilities 
      Jugal Garg, Ruta Mehta, Milind Sohoni, Vijay V. Vazirani
    • Making Polynomials Robust to Noise 
      Alexander A. Sherstov
    • Online matching with concave returns 
      Nikhil R. Devanur, Kamal Jain
    • Learning Poisson Binomial Distributions [arXiv]
      Constantinos Daskalakis, Ilias Diakonikolas, Rocco Servedio
    • Homomorphic encryption from codes [pdf]
      Andrej Bogdanov, Chin Ho Lee
    • Tight bounds on computing error-correcting codes by bounded-depth circuits with arbitrary gates [pdf]
      Anna Gal, Kristoffer Arnsfelt Hansen, Michal Koucky, Pavel Pudlak, Emanuele Viola
    • Polyhedral Clinching Auctions and the Adwords Polytope [arXiv]
      Gagan Goel, Vahab Mirrokni, Renato Paes Leme
    • Complexity of Counting CSP with Complex Weights [arXiv]
      Jin-Yi Cai, Xi Chen
    • Beating Randomized Response on Incoherent Matrices [arXiv]
      Moritz Hardt, Aaron Roth
    • The Multiparty Communication Complexity of Set Disjointness [arXiv]
      Alexander A. Sherstov
    • Nearly Optimal Sparse Fourier Transform [arXiv]
      Haitham Hassanieh, Piotr Indyk, Dina Katabi, Eric Price
    • Certifiable Quantum Dice — Or, testable exponential randomness expansion [arXiv]
      Umesh Vazirani, Thomas Vidick
    • Prior-Free Auctions with Ordered Bidders 
      Stefano Leonardi, Tim Roughgarden
    • Using Petal-Decompositions to Build a Low Stretch Spanning Tree 
      Ittai Abraham, Ofer Neiman
    • On Identity Testing of Tensors, Low-rank Recovery and Compressed Sensing [arXiv]
      Michael A. Forbes, Amir Shpilka
    • The traveling salesman problem: low dimensionality implies a polynomial time approximation scheme [arXiv]
      Yair Bartal, Lee-Ad Gottlieb, Robert Krauthgamer
    • Competitive Contagion in Networks [arXiv]
      Sanjeev Goyal, Michael Kearns
    • Jacobian hit circuits: Hitting sets, lower bounds for depth-D occur-k formulas and depth-3 transcendence degree-k circuits [arXiv]
      Manindra Agrawal, Chandan Saha, Ramprasad Saptharishi, Nitin Saxena
    • A new point of NP-hardness for Unique Games [pdf]
      Ryan O’Donnell, John Wright
    • Approximation Algorithms for Semi-random Graph Partitioning Problems 
      Konstantin Makarychev, Yury Makarychev, Aravindan Vijayaraghavan
    • Structure Theorem and Isomorphism Test for Graphs with Excluded Topological Subgraphs [arXiv]
      Martin Grohe, Daniel Marx
    • On the limits of black-box reductions in mechanism design 
      Shuchi Chawla, Nicole Immorlica, Brendan Lucier
    • Fully Dynamic Approximate Distance Oracles for Planar Graphs via Forbidden-Set Distance labels
      Ittai Abraham, Shiri Chechik, Cyril Gavoille
    • Affine Projections of Polynomials [ECCC]
      Neeraj Kayal
    • From Query Complexity to Computational Complexity [pdf]
      Shahar Dobzinski, Jan Vondrak
    • Multiparty Computation Secure Against Continual Memory Leakage 
      Elette Boyle, Shafi Goldwasser, Abhishek Jain, Yael Tauman Kalai
    • Multiway spectral partitioning and higher-order Cheeger inequalities [arXiv]
      Shayan Oveis Gharan, James R. Lee, Luca Trevisan
    • Budget Feasible Mechanism Design: From Prior-Free to Bayesian 
      Xiaohui Bei, Ning Chen, Nick Gravin, Pinyan Lu
    • Nearly optimal solutions for the Chow Parameters Problem and low- weight approximation of halfspaces 
      Anindya De, Ilias Diakonikolas, Vitaly Feldman, Rocco Servedio
    • The freezing threshold for k-colourings of a random graph 
      Michael Molloy
    • Tight lower bounds for the online labelling problem [arXiv]
      Jan Bulanek, Michal Koucky, Michael Saks
    • Computing a Nonnegative Matrix Factorization – Provably [arXiv]
      Sanjeev Arora, Rong Ge, Ravi Kannan, Ankur Moitra
    • Many Sparse Cuts via Higher Eigenvalues [arXiv]
      Anand Louis, Prasad Raghavendra, Prasad Tetali, Santosh Vempala
    • A Rigorous Analyis of One-Dimensional Schelling Segregation 
      Christina Brandt, Nicole Immorlica, Gautam Kamath, Robert Kleinberg
    • A Near-Linear Time $\eps$-Approximation Algorithm for Geometric Bipartite Matching [pdf]
      R. Sharathkumar, Pankaj K. Agarwal
    • Matroid Prophet Inequalities [arXiv]
      Robert Kleinberg, Matthew Weinberg
    • Rational Proofs 
      Pablo Azar, Silvio Micali
    • Robust satisfiability of constraint satisfaction problems [ECCC]
      Libor Barto, Marcin Kozik
    • On-the-Fly Multiparty Computation on the Cloud via Multikey Fully Homomorphic Encryption 
      Adriana Lopez-Alt, Eran Tromer, Vinod Vaikuntanathan
    • Polynomial Time Algorithms for Multi-Type Branching Processes and Stochastic Context-Free Grammars [arXiv]
      Kousha Etessami, Alistair Stewart, Mihalis Yannakakis
    • Unconditionally Differentially Private Mechanisms for Linear Queries 
      Aditya Bhaskara, Daniel Dadush, Ravishankar Krishnaswamy, Kunal Talwar
    • Multiplying Matrices Faster Than Coppersmith-Winograd [pdf]
      Virginia Vassilevska Williams
    • Matroids and Integrality Gaps for Hypergraphic Steiner Tree Relaxations [arXiv]
      Michel X. Goemans, Neil Olver, Thomas Rothvoss, Rico Zenklusen
    • Minimax Option Pricing Meets Black-Scholes in the Limit [arXiv]
      Jacob Abernethy, Rafael Frongillo, Andre Wibisono
    • Characterizing Pseudoentropy and Simplifying Pseudorandom Generator Constructions [ECCC]
      Salil Vadhan, Colin Jia Zheng
    • Optmal Online Buffer Scheduling for Block Devices 
      Anna Adamaszek, Artur Czumaj, Matthias Englert, Harald Raecke
    • On the Virtue of Succinct Proofs: Amplifying Communication Complexity Hardness to Time-Space Trade-offs in Proof Complexity 
      Trinh Huynh, Jacob Nordstrom
    • Strict Fibonacci Heaps 
      Gerth Stolting Brodal, George Lagogiannis, Robert E. Tarjan
    • Design Extractors, Non-Malleable Condensers and Privacy Amplification [ECCC]
      Xin Li
    • Optimal Private Halfspace Counting via Discrepancy 
      S. Muthukrishnan, Aleksandar Nikolov
    • Beyond Laplacians: Faster Approximations of Multicommodity Flow in Undirected Graphs Using Quadratically Coupled Electrical Flows 
      Jonathan A. Kelner, Gary L. Miller, Richard Peng
    • An Algorithmic Characerization of Multi-Dimensional Mechanisms [arXiv]
      Yang Cai, Constantinos Deskalakis, S. Matthew Weinberg
    • Tight Time-Space Tradeoff for Mutual Exclusion 
      Nikhil Bansal, Vibhor Bhatt, Prasad Jayanti, Ranganath Kondapally
    • Hypercontractivity, Sum-of-Squares Proofs, and their Applications 
      Boaz Barak, Aram W. Harrow, Jonathan Kelner, David Steurer, Yuan Zhou
    • Tight RMR Lower Bounds for Randomized Mutual Exclusion George Giakkoupis, Philipp Woelfel