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

Advertisements