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

Shahar Dobzinski, Jan Vondrak: From Query Complexity to Computational Complexity –> http://theory.stanford.edu/~jvondrak/data/querytocc.pdf

Hi Shiva,

I thought of the following method to encourage publishing the paper (especially in light of the recent Elsevier boycott): mention in your list ONLY the papers that are publicly accessible.

Dan.

Hi Dan,

Sometimes authors wait for reviewers’ comments, so that they can incorporate the changes suggested by reviewers before making their paper public.

-Shiva

We have a long way to make the community of TCS “open-access”.

If we don’t make steps towards there, it won’t happen.

I do not question the various reasons (I would really call it excuses) why authors wouldn’t post the papers – now, before submitting, or never.

BUT: you sent the paper to STOC and it got accepted? POST YOUR PAPER!

If not, your paper won’t be in the list of files with pdfs on this blog, that’s it.

Dan.

I second Dan!

This list is a compilation of PDF’s. If someone just wants to see the list of accepted papers, they can go to the STOC site instead.

Another alternative is to have two lists, one only with those papers available online, and the other like the one you have now.

Two more:

Vassilevska Williams: http://www.cs.berkeley.edu/~virgi/matrixmult.pdf

Abernethy et al.: http://arxiv.org/abs/1202.2585