| 2012 | 2 Subhash Khot, Preyas Popat, Nisheeth K. Vishnoi |
| 2012 | A complementary pivot algorithm for markets under separable, piecewise-linear concave utilities. Jugal Garg, Ruta Mehta, Milind A. Sohoni, Vijay V. Vazirani |
| 2012 | A near-linear time ε-approximation algorithm for geometric bipartite matching. R. Sharathkumar, Pankaj K. Agarwal |
| 2012 | A new point of NP-hardness for unique games. Ryan O'Donnell, John Wright |
| 2012 | A quantitative gibbard-satterthwaite theorem without neutrality. Elchanan Mossel, Miklós Z. Rácz |
| 2012 | A tight RMR lower bound for randomized mutual exclusion. George Giakkoupis, Philipp Woelfel |
| 2012 | Affine projections of polynomials: extended abstract. Neeraj Kayal |
| 2012 | An algorithmic characterization of multi-dimensional mechanisms. Yang Cai, Constantinos Daskalakis, S. Matthew Weinberg |
| 2012 | An analysis of one-dimensional schelling segregation. Christina Brandt, Nicole Immorlica, Gautam Kamath, Robert Kleinberg |
| 2012 | Approximating the exponential, the lanczos method and an Õ( Lorenzo Orecchia, Sushant Sachdeva, Nisheeth K. Vishnoi |
| 2012 | Approximation algorithms and hardness of integral concurrent flow. Parinya Chalermsook, Julia Chuzhoy, Alina Ene, Shi Li |
| 2012 | Approximation algorithms for semi-random partitioning problems. Konstantin Makarychev, Yury Makarychev, Aravindan Vijayaraghavan |
| 2012 | Beating randomized response on incoherent matrices. Moritz Hardt, Aaron Roth |
| 2012 | Budget feasible mechanism design: from prior-free to bayesian. Xiaohui Bei, Ning Chen, Nick Gravin, Pinyan Lu |
| 2012 | Catching the k-NAESAT threshold. Amin Coja-Oghlan, Konstantinos Panagiotou |
| 2012 | Certifiable quantum dice: or, true random number generation secure against quantum adversaries. Umesh V. Vazirani, Thomas Vidick |
| 2012 | Characterizing pseudoentropy and simplifying pseudorandom generator constructions. Salil P. Vadhan, Colin Jia Zheng |
| 2012 | Competitive contagion in networks. Sanjeev Goyal, Michael J. Kearns |
| 2012 | Complexity of counting CSP with complex weights. Jin-Yi Cai, Xi Chen |
| 2012 | Computing a nonnegative matrix factorization - provably. Sanjeev Arora, Rong Ge, Ravindran Kannan, Ankur Moitra |
| 2012 | Design extractors, non-malleable condensers and privacy amplification. Xin Li |
| 2012 | Determinism versus nondeterminism with arithmetic tests and computation: extended abstract. Miklós Ajtai |
| 2012 | Edge transitive ramanujan graphs and symmetric LDPC good codes. Tali Kaufman, Alexander Lubotzky |
| 2012 | Fast matrix rank algorithms and applications. Ho Yee Cheung, Tsz Chiu Kwok, Lap Chi Lau |
| 2012 | Faster approximate multicommodity flow using quadratically coupled flows. Jonathan A. Kelner, Gary L. Miller, Richard Peng |
| 2012 | Finding red balloons with split contracts: robustness to individuals' selfishness. Manuel Cebrián, Lorenzo Coviello, Andrea Vattani, Panagiotis Voulgaris |
| 2012 | Folded codes from function field towers and improved optimal rate list decoding. Venkatesan Guruswami, Chaoping Xing |
| 2012 | From irreducible representations to locally decodable codes. Klim Efremenko |
| 2012 | From query complexity to computational complexity. Shahar Dobzinski, Jan Vondrák |
| 2012 | Fully dynamic approximate distance oracles for planar graphs via forbidden-set distance labels. Ittai Abraham, Shiri Chechik, Cyril Gavoille |
| 2012 | Global computation in a poorly connected world: fast rumor spreading with no dependence on conductance. Keren Censor-Hillel, Bernhard Haeupler, Jonathan A. Kelner, Petar Maymounkov |
| 2012 | Hypercontractivity, sum-of-squares proofs, and their applications. Boaz Barak, Fernando G. S. L. Brandão, Aram W. Harrow, Jonathan A. Kelner, David Steurer, Yuan Zhou |
| 2012 | Improved smoothed analysis of multiobjective optimization. Tobias Brunsch, Heiko Röglin |
| 2012 | Improving christofides' algorithm for the s-t path TSP. Hyung-Chan An, Robert Kleinberg, David B. Shmoys |
| 2012 | Interactive information complexity. Mark Braverman |
| 2012 | Jacobian hits circuits: hitting-sets, lower bounds for depth-D occur-k formulas & depth-3 transcendence degree-k circuits. Manindra Agrawal, Chandan Saha, Ramprasad Saptharishi, Nitin Saxena |
| 2012 | Learning poisson binomial distributions. Constantinos Daskalakis, Ilias Diakonikolas, Rocco A. Servedio |
| 2012 | Linear vs. semidefinite extended formulations: exponential separation and strong lower bounds. Samuel Fiorini, Serge Massar, Sebastian Pokutta, Hans Raj Tiwary, Ronald de Wolf |
| 2012 | Making polynomials robust to noise. Alexander A. Sherstov |
| 2012 | Many sparse cuts via higher eigenvalues. Anand Louis, Prasad Raghavendra, Prasad Tetali, Santosh S. Vempala |
| 2012 | Matroid prophet inequalities. Robert Kleinberg, S. Matthew Weinberg |
| 2012 | Matroids and integrality gaps for hypergraphic steiner tree relaxations. Michel X. Goemans, Neil Olver, Thomas Rothvoß, Rico Zenklusen |
| 2012 | Minimax option pricing meets black-scholes in the limit. Jacob D. Abernethy, Rafael M. Frongillo, Andre Wibisono |
| 2012 | Monotone expansion. Jean Bourgain, Amir Yehudayoff |
| 2012 | Multi-way spectral partitioning and higher-order cheeger inequalities. James R. Lee, Shayan Oveis Gharan, Luca Trevisan |
| 2012 | Multiparty computation secure against continual memory leakage. Elette Boyle, Shafi Goldwasser, Abhishek Jain, Yael Tauman Kalai |
| 2012 | Multiplying matrices faster than coppersmith-winograd. Virginia Vassilevska Williams |
| 2012 | Nearly complete graphs decomposable into large induced matchings and their applications. Noga Alon, Ankur Moitra, Benny Sudakov |
| 2012 | Nearly optimal solutions for the chow parameters problem and low-weight approximation of halfspaces. Anindya De, Ilias Diakonikolas, Vitaly Feldman, Rocco A. Servedio |
| 2012 | Nearly optimal sparse fourier transform. Haitham Hassanieh, Piotr Indyk, Dina Katabi, Eric Price |
| 2012 | On identity testing of tensors, low-rank recovery and compressed sensing. Michael A. Forbes, Amir Shpilka |
| 2012 | On the limits of black-box reductions in mechanism design. Shuchi Chawla, Nicole Immorlica, Brendan Lucier |
| 2012 | On the virtue of succinct proofs: amplifying communication complexity hardness to time-space trade-offs in proof complexity. Trinh Huynh, Jakob Nordström |
| 2012 | On vertex sparsifiers with Steiner nodes. Julia Chuzhoy |
| 2012 | On-the-fly multiparty computation on the cloud via multikey fully homomorphic encryption. Adriana López-Alt, Eran Tromer, Vinod Vaikuntanathan |
| 2012 | Online matching with concave returns. Nikhil R. Devanur, Kamal Jain |
| 2012 | Optimal online buffer scheduling for block devices. Anna Adamaszek, Artur Czumaj, Matthias Englert, Harald Räcke |
| 2012 | Optimal private halfspace counting via discrepancy. S. Muthukrishnan, Aleksandar Nikolov |
| 2012 | Polyhedral clinching auctions and the adwords polytope. Gagan Goel, Vahab S. Mirrokni, Renato Paes Leme |
| 2012 | Polynomial time algorithms for multi-type branching processesand stochastic context-free grammars. Kousha Etessami, Alistair Stewart, Mihalis Yannakakis |
| 2012 | Prior-free auctions with ordered bidders. Stefano Leonardi, Tim Roughgarden |
| 2012 | Probabilistic existence of rigid combinatorial structures. Greg Kuperberg, Shachar Lovett, Ron Peled |
| 2012 | Proceedings of the 44th Symposium on Theory of Computing Conference, STOC 2012, New York, NY, USA, May 19 - 22, 2012 Howard J. Karloff, Toniann Pitassi |
| 2012 | Pseudorandom generators with long stretch and low locality from random local one-way functions. Benny Applebaum |
| 2012 | Quantum money from hidden subspaces. Scott Aaronson, Paul F. Christiano |
| 2012 | Rational proofs. Pablo Daniel Azar, Silvio Micali |
| 2012 | Reconstruction of depth-4 multilinear circuits with top fan-in 2. Ankit Gupta, Neeraj Kayal, Satyanarayana V. Lokam |
| 2012 | Robust satisfiability of constraint satisfaction problems. Libor Barto, Marcin Kozik |
| 2012 | Routing in undirected graphs with constant congestion. Julia Chuzhoy |
| 2012 | Separating multilinear branching programs and formulas. Zeev Dvir, Guillaume Malod, Sylvain Perifel, Amir Yehudayoff |
| 2012 | Short proofs for the determinant identities. Pavel Hrubes, Iddo Tzameret |
| 2012 | Solution of the propeller conjecture in R Steven Heilman, Aukosh Jagannath, Assaf Naor |
| 2012 | Span programs for functions with constant-sized 1-certificates: extended abstract. Aleksandrs Belovs |
| 2012 | Strict fibonacci heaps. Gerth Stølting Brodal, George Lagogiannis, Robert Endre Tarjan |
| 2012 | Strongly polynomial algorithm for a class of minimum-cost flow problems with separable convex objectives. László A. Végh |
| 2012 | Structure theorem and isomorphism test for graphs with excluded topological subgraphs. Martin Grohe, Dániel Marx |
| 2012 | Subspace evasive sets. Zeev Dvir, Shachar Lovett |
| 2012 | The cell probe complexity of dynamic range counting. Kasper Green Larsen |
| 2012 | The freezing threshold for k-colourings of a random graph. Michael Molloy |
| 2012 | The multiparty communication complexity of set disjointness. Alexander A. Sherstov |
| 2012 | The traveling salesman problem: low-dimensionality implies a polynomial time approximation scheme. Yair Bartal, Lee-Ad Gottlieb, Robert Krauthgamer |
| 2012 | Tight bounds for distributed functional monitoring. David P. Woodruff, Qin Zhang |
| 2012 | Tight bounds for monotone switching networks via fourier analysis. Siu Man Chan, Aaron Potechin |
| 2012 | Tight bounds on computing error-correcting codes by bounded-depth circuits with arbitrary gates. Anna Gál, Kristoffer Arnsfelt Hansen, Michal Koucký, Pavel Pudlák, Emanuele Viola |
| 2012 | Tight lower bounds for the online labeling problem. Jan Bulánek, Michal Koucký, Michael E. Saks |
| 2012 | Tight time-space tradeoff for mutual exclusion. Nikhil Bansal, Vibhor Bhatt, Prasad Jayanti, Ranganath Kondapally |
| 2012 | Time-space tradeoffs in resolution: superpolynomial lower bounds for superlinear space. Paul Beame, Christopher Beck, Russell Impagliazzo |
| 2012 | Unconditional differentially private mechanisms for linear queries. Aditya Bhaskara, Daniel Dadush, Ravishankar Krishnaswamy, Kunal Talwar |
| 2012 | Using petal-decompositions to build a low stretch spanning tree. Ittai Abraham, Ofer Neiman |
| 2012 | When the cut condition is enough: a complete characterization for multiflow problems in series-parallel networks. Amit Chakrabarti, Lisa Fleischer, Christophe Weibel |