| 2012 | Popularity vs maximum cardinality in the stable marriage setting. | Telikepalli Kavitha |
| 2012 | The maximum number of faces of the Minkowski sum of two convex polytopes. | Menelaos I. Karavelas, Eleni Tzanaki |
| 2012 | Submatrix maximum queries in Monge matrices and Monge partial matrices, and their applications. | Haim Kaplan, Shay Mozes, Yahav Nussbaum, Micha Sharir |
| 2012 | Sparser Johnson-Lindenstrauss transforms. | Daniel M. Kane, Jelani Nelson |
| 2012 | Approximate tree decompositions of planar graphs in linear time. | Frank Kammer, Torsten Tholey |
| 2012 | Finding an induced path of given parity in planar graphs in polynomial time. | Marcin Kaminski, Naomi Nishimura |
| 2012 | Erds-Psa property and its algorithmic applications: parity constraints, subset feedback set, and subset packing. | Naonori Kakimura, Ken-ichi Kawarabayashi, Yusuke Kobayashi |
| 2012 | Expanders are universal for the class of all spanning trees. | Daniel Johannsen, Michael Krivelevich, Wojciech Samotij |
| 2012 | A satisfiability algorithm for AC | Russell Impagliazzo, William Matthews, Ramamohan Paturi |
| 2012 | Online scheduling with general cost functions. | Sungjin Im, Benjamin Moseley, Kirk Pruhs |
| 2012 | The set of solutions of random XORSAT formulae. | Morteza Ibrahimi, Yashodhan Kanoria, Matt Kraning, Andrea Montanari |
| 2012 | Using hashing to solve the dictionary problem. | John Iacono, Mihai Patrascu |
| 2012 | Efficient algorithms for maximum weight matchings in general graphs with small edge weights. | Chien-Chung Huang, Telikepalli Kavitha |
| 2012 | Weak compositions and their applications to polynomial lower bounds for kernelization. | Danny Hermelin, Xi Wu |
| 2012 | Simple and practical algorithm for sparse Fourier transform. | Haitham Hassanieh, Piotr Indyk, Dina Katabi, Eric Price |
| 2012 | Private data release via learning thresholds. | Moritz Hardt, Guy N. Rothblum, Rocco A. Servedio |
| 2012 | Wireless connectivity and capacity. | Magns M. Halldrsson, Pradipta Mitra |
| 2012 | Mechanism design via consensus estimates, cross checking, and profit extraction. | Bach Q. Ha, Jason D. Hartline |
| 2012 | Optimal column-based low-rank matrix reconstruction. | Venkatesan Guruswami, Ali Kemal Sinop |
| 2012 | Bypassing UGC from some optimal geometric inapproximability results. | Venkatesan Guruswami, Prasad Raghavendra, Rishi Saket, Yi Wu |
| 2012 | Approximation algorithms for stochastic orienteering. | Anupam Gupta, Ravishankar Krishnaswamy, Viswanath Nagarajan, R. Ravi |
| 2012 | Scheduling heterogeneous processors isn't as easy as you think. | Anupam Gupta, Sungjin Im, Ravishankar Krishnaswamy, Benjamin Moseley, Kirk Pruhs |
| 2012 | Structural and logical approaches to the graph isomorphism problem. | Martin Grohe |
| 2012 | Privacy-preserving group data access via stateless oblivious RAM simulation. | Michael T. Goodrich, Michael Mitzenmacher, Olga Ohrimenko, Roberto Tamassia |
| 2012 | On the communication and streaming complexity of maximum bipartite matching. | Ashish Goel, Michael Kapralov, Sanjeev Khanna |