| 2012 | 53rd Annual IEEE Symposium on Foundations of Computer Science, FOCS 2012, New Brunswick, NJ, USA, October 20-23, 2012 |
| 2012 | A Direct Product Theorem for the Two-Party Bounded-Round Public-Coin Communication Complexity. Rahul Jain, Attila Pereszlényi, Penghui Yao |
| 2012 | A Multi-prover Interactive Proof for NEXP Sound against Entangled Provers. Tsuyoshi Ito, Thomas Vidick |
| 2012 | A New Direction for Counting Perfect Matchings. Taisuke Izumi, Tadashi Wadayama |
| 2012 | A New Infinity of Distance Oracles for Sparse Graphs. Mihai Patrascu, Liam Roditty, Mikkel Thorup |
| 2012 | A PTAS for Computing the Supremum of Gaussian Processes. Raghu Meka |
| 2012 | A Permanent Approach to the Traveling Salesman Problem. Nisheeth K. Vishnoi |
| 2012 | A Polylogarithmic Approximation Algorithm for Edge-Disjoint Paths with Congestion 2. Julia Chuzhoy, Shi Li |
| 2012 | A Structure Theorem for Poorly Anticoncentrated Gaussian Chaoses and Applications to the Study of Polynomial Threshold Functions. Daniel M. Kane |
| 2012 | A Tight Combinatorial Algorithm for Submodular Maximization Subject to a Matroid Constraint. Yuval Filmus, Justin Ward |
| 2012 | A Tight Linear Time (1/2)-Approximation for Unconstrained Submodular Maximization. Niv Buchbinder, Moran Feldman, Joseph Naor, Roy Schwartz |
| 2012 | A Weight-Scaling Algorithm for Min-Cost Imperfect Matchings in Bipartite Graphs. Lyle Ramshaw, Robert Endre Tarjan |
| 2012 | Active Property Testing. Maria-Florina Balcan, Eric Blais, Avrim Blum, Liu Yang |
| 2012 | Algorithmic Applications of Baur-Strassen's Theorem: Shortest Cycles, Diameter and Matchings. Marek Cygan, Harold N. Gabow, Piotr Sankowski |
| 2012 | Almost Optimal Canonical Property Testers for Satisfiability. Christian Sohler |
| 2012 | An Additive Combinatorics Approach Relating Rank to Communication Complexity. Eli Ben-Sasson, Shachar Lovett, Noga Ron-Zewi |
| 2012 | Approximating the Expansion Profile and Almost Optimal Local Graph Clustering. Shayan Oveis Gharan, Luca Trevisan |
| 2012 | Approximation Limits of Linear Programs (Beyond Hierarchies). Gábor Braun, Samuel Fiorini, Sebastian Pokutta, David Steurer |
| 2012 | Beck's Three Permutations Conjecture: A Counterexample and Some Consequences. Alantha Newman, Ofer Neiman, Aleksandar Nikolov |
| 2012 | Better Pseudorandom Generators from Milder Pseudorandom Restrictions. Parikshit Gopalan, Raghu Meka, Omer Reingold, Luca Trevisan, Salil P. Vadhan |
| 2012 | Combinatorial Coloring of 3-Colorable Graphs. Ken-ichi Kawarabayashi, Mikkel Thorup |
| 2012 | Computing Multiplicities of Lie Group Representations. Matthias Christandl, Brent Doran, Michael Walter |
| 2012 | Concave Generalized Flows with Applications to Market Equilibria. László A. Végh |
| 2012 | Constructing Non-malleable Commitments: A Black-Box Approach. Vipul Goyal, Chen-Kuei Lee, Rafail Ostrovsky, Ivan Visconti |
| 2012 | Constructing a Pseudorandom Generator Requires an Almost Linear Number of Calls. Thomas Holenstein, Makrand Sinha |
| 2012 | Constructive Discrepancy Minimization by Walking on the Edges. Shachar Lovett, Raghu Meka |
| 2012 | Designing FPT Algorithms for Cut Problems Using Randomized Contractions. Rajesh Hemant Chitnis, Marek Cygan, MohammadTaghi Hajiaghayi, Marcin Pilipczuk, Michal Pilipczuk |
| 2012 | Down the Rabbit Hole: Robust Proximity Search and Density Estimation in Sublinear Space. Sariel Har-Peled, Nirman Kumar |
| 2012 | Efficient Interactive Coding against Adversarial Noise. Zvika Brakerski, Yael Tauman Kalai |
| 2012 | Everywhere-Sparse Spanners via Dense Subgraphs. Eden Chlamtac, Michael Dinitz, Robert Krauthgamer |
| 2012 | Faster Algorithms for Rectangular Matrix Multiplication. François Le Gall |
| 2012 | Faster SDP Hierarchy Solvers for Local Rounding Algorithms. Venkatesan Guruswami, Ali Kemal Sinop |
| 2012 | Finding Correlations in Subquadratic Time, with Applications to Learning Parities and Juntas. Gregory Valiant |
| 2012 | Formulas Resilient to Short-Circuit Errors. Yael Tauman Kalai, Allison B. Lewko, Anup Rao |
| 2012 | From the Impossibility of Obfuscation to a New Non-Black-Box Simulation Technique. Nir Bitansky, Omer Paneth |
| 2012 | Geometric Complexity Theory V: Equivalence between Blackbox Derandomization of Polynomial Identity Testing and Derandomization of Noether's Normalization Lemma. Ketan Mulmuley |
| 2012 | Hardness of Finding Independent Sets in Almost q-Colorable Graphs. Subhash Khot, Rishi Saket |
| 2012 | Higher Cell Probe Lower Bounds for Evaluating Polynomials. Kasper Green Larsen |
| 2012 | How to Allocate Tasks Asynchronously. Dan Alistarh, Michael A. Bender, Seth Gilbert, Rachid Guerraoui |
| 2012 | How to Compute in the Presence of Leakage. Shafi Goldwasser, Guy N. Rothblum |
| 2012 | How to Construct Quantum Random Functions. Mark Zhandry |
| 2012 | Improved Distance Sensitivity Oracles via Fast Single-Source Replacement Paths. Fabrizio Grandoni, Virginia Vassilevska Williams |
| 2012 | Iterative Rounding Approximation Algorithms for Degree-Bounded Node-Connectivity Network Design. Takuro Fukunaga, R. Ravi |
| 2012 | LP Rounding for k-Centers with Non-uniform Hard Capacities. Marek Cygan, MohammadTaghi Hajiaghayi, Samir Khuller |
| 2012 | Large Deviation Bounds for Decision Trees and Sampling Lower Bounds for AC0-Circuits. Chris Beck, Russell Impagliazzo, Shachar Lovett |
| 2012 | Learning Topic Models - Going beyond SVD. Sanjeev Arora, Rong Ge, Ankur Moitra |
| 2012 | Learning-Graph-Based Quantum Algorithm for k-Distinctness. Aleksandrs Belovs |
| 2012 | Lower Bounds on Information Complexity via Zero-Communication Protocols and Applications. Iordanis Kerenidis, Sophie Laplante, Virginie Lerays, Jérémie Roland, David Xiao |
| 2012 | Lower Bounds on Interactive Compressibility by Constant-Depth Circuits. Arkadev Chattopadhyay, Rahul Santhanam |
| 2012 | Making the Long Code Shorter. Boaz Barak, Parikshit Gopalan, Johan Håstad, Raghu Meka, Prasad Raghavendra, David Steurer |
| 2012 | Matching with Our Eyes Closed. Gagan Goel, Pushkar Tripathi |
| 2012 | New Limits to Classical and Quantum Instance Compression. Andrew Drucker |
| 2012 | Non-malleable Extractors, Two-Source Extractors and Privacy Amplification. Xin Li |
| 2012 | On Range Searching with Semialgebraic Sets II. Pankaj K. Agarwal, Jirí Matousek, Micha Sharir |
| 2012 | On the Complexity of Finding Narrow Proofs. Christoph Berkholz |
| 2012 | On the Homotopy Test on Surfaces. Francis Lazarus, Julien Rivaud |
| 2012 | On-Line Indexing for General Alphabets via Predecessor Queries on Subsets of an Ordered List. Tsvi Kopelowitz |
| 2012 | Online Matching with Stochastic Rewards. Aranyak Mehta, Debmalya Panigrahi |
| 2012 | Optimal Multi-dimensional Mechanism Design: Reducing Revenue to Welfare Maximization. Yang Cai, Constantinos Daskalakis, S. Matthew Weinberg |
| 2012 | Partially Symmetric Functions Are Efficiently Isomorphism-Testable. Eric Blais, Amit Weinstein, Yuichi Yoshida |
| 2012 | Planar F-Deletion: Approximation, Kernelization and Optimal FPT Algorithms. Fedor V. Fomin, Daniel Lokshtanov, Neeldhara Misra, Saket Saurabh |
| 2012 | Population Recovery and Partial Identification. Avi Wigderson, Amir Yehudayoff |
| 2012 | Positive Results for Concurrently Secure Computation in the Plain Model. Vipul Goyal |
| 2012 | Pseudorandomness from Shrinkage. Russell Impagliazzo, Raghu Meka, David Zuckerman |
| 2012 | Quasi-optimal Multiplication of Linear Differential Operators. Alexandre Benoît, Alin Bostan, Joris van der Hoeven |
| 2012 | Randomized Greedy Algorithms for the Maximum Matching Problem with New Analysis. Matthias Poloczek, Mario Szegedy |
| 2012 | Rarity for Semimeasures. Leonid A. Levin |
| 2012 | Representative Sets and Irrelevant Vertices: New Tools for Kernelization. Stefan Kratsch, Magnus Wahlström |
| 2012 | Single Source - All Sinks Max Flows in Planar Digraphs. Jakub Lacki, Yahav Nussbaum, Piotr Sankowski, Christian Wulff-Nilsen |
| 2012 | Sparse Affine-Invariant Linear Codes Are Locally Testable. Eli Ben-Sasson, Noga Ron-Zewi, Madhu Sudan |
| 2012 | Split and Join: Strong Partitions and Universal Steiner Trees for Graphs. Costas Busch, Chinmoy Dutta, Jaikumar Radhakrishnan, Rajmohan Rajaraman, Srinivasagopalan Srivathsan |
| 2012 | The Computational Hardness of Counting in Two-Spin Models on d-Regular Graphs. Allan Sly, Nike Sun |
| 2012 | The Cutting Plane Method Is Polynomial for Perfect Matchings. Karthekeyan Chandrasekaran, László A. Végh, Santosh S. Vempala |
| 2012 | The Dynamics of Influence Systems. Bernard Chazelle |
| 2012 | The Exponential Mechanism for Social Welfare: Private, Truthful, and Nearly Optimal. Zhiyi Huang, Sampath Kannan |
| 2012 | The Johnson-Lindenstrauss Transform Itself Preserves Differential Privacy. Jeremiah Blocki, Avrim Blum, Anupam Datta, Or Sheffet |
| 2012 | The Locality of Distributed Symmetry Breaking. Leonid Barenboim, Michael Elkin, Seth Pettie, Johannes Schneider |
| 2012 | The Power of Linear Programming for Valued CSPs. Johan Thapper, Stanislav Zivný |
| 2012 | The Privacy of the Analyst and the Power of the State. Cynthia Dwork, Moni Naor, Salil P. Vadhan |
| 2012 | The Tile Assembly Model is Intrinsically Universal. David Doty, Jack H. Lutz, Matthew J. Patitz, Robert T. Schweller, Scott M. Summers, Damien Woods |
| 2012 | Tight Bounds for Randomized Load Balancing on Arbitrary Network Topologies. Thomas Sauerwald, He Sun |