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