| 2012 | Solving Planar k -Terminal Cut in $O(n^{c \sqrt{k}})$ Time. | Philip N. Klein, Dniel Marx |
| 2012 | Quantum Adversary (Upper) Bound. | Shelby Kimmel |
| 2012 | Exponential Lower Bounds and Separation for Query Rewriting. | Stanislav Kikot, Roman Kontchakov, Vladimir V. Podolskii, Michael Zakharyaschev |
| 2012 | NNS Lower Bounds via Metric Expansion for l ∞ and EMD. | Michael Kapralov, Rina Panigrahy |
| 2012 | Counting Arbitrary Subgraphs in Data Streams. | Daniel M. Kane, Kurt Mehlhorn, Thomas Sauerwald, He Sun |
| 2012 | Faster Fully Compressed Pattern Matching by Recompression. | Artur Jez |
| 2012 | Improving Quantum Query Complexity of Boolean Matrix Multiplication Using Graph Collision. | Stacey Jeffery, Robin Kothari, Frdric Magniez |
| 2012 | CRAM: Compressed Random Access Memory. | Jesper Jansson, Kunihiko Sadakane, Wing-Kin Sung |
| 2012 | Topology-Aware VM Migration in Bandwidth Oversubscribed Datacenter Networks. | Navendu Jain, Ishai Menache, Joseph Naor, F. Bruce Shepherd |
| 2012 | Constant-Time Algorithms for Sparsity Matroids. | Hiro Ito, Shin-ichi Tanigawa, Yuichi Yoshida |
| 2012 | Minimum Latency Submodular Cover. | Sungjin Im, Viswanath Nagarajan, Ruben van der Zwaan |
| 2012 | A Thirty Year Old Conjecture about Promise Problems. | Andrew Hughes, Aduri Pavan, Nathan Russell, Alan L. Selman |
| 2012 | Distributed Private Heavy Hitters. | Justin Hsu, Sanjeev Khanna, Aaron Roth |
| 2012 | Session Types and Distributed Computing. | Kohei Honda |
| 2012 | Standing on the Shoulders of a Giant - One Persons Experience of Turings Impact (Summary of the Alan M. Turing Lecture). | David Harel |
| 2012 | Streaming and Communication Complexity of Clique Approximation. | Magns M. Halldrsson, Xiaoming Sun, Mario Szegedy, Chengu Wang |
| 2012 | Approximating Sparse Covering Integer Programs Online. | Anupam Gupta, Viswanath Nagarajan |
| 2012 | The Online Metric Matching Problem for Doubling Metrics. | Anupam Gupta, Kevin Lewi |
| 2012 | Random Hyperbolic Graphs: Degree Sequence and Clustering - (Extended Abstract). | Luca Gugelmann, Konstantinos Panagiotou, Ueli Peter |
| 2012 | Byzantine Agreement with a Rational Adversary. | Adam Groce, Jonathan Katz, Aishwarya Thiruvengadam, Vassilis Zikas |
| 2012 | Stochastic Vehicle Routing with Recourse. | Inge Li Grtz, Viswanath Nagarajan, Rishi Saket |
| 2012 | Anonymous Card Shuffling and Its Applications to Parallel Mixnets. | Michael T. Goodrich, Michael Mitzenmacher |
| 2012 | The Complexity of Computing the Sign of the Tutte Polynomial (and Consequent #P-hardness of Approximation). | Leslie Ann Goldberg, Mark Jerrum |
| 2012 | Hardness of Approximation for Quantum Problems. | Sevag Gharibian, Julia Kempe |
| 2012 | Dominators, Directed Bipolar Orders, and Independent Spanning Trees. | Loukas Georgiadis, Robert Endre Tarjan |