| 2012 | Top- | Gonzalo Navarro, Yakov Nekrich |
| 2012 | Exact distance oracles for planar graphs. | Shay Mozes, Christian Sommer |
| 2012 | Outperforming LRU via competitive analysis on parametrized inputs for paging. | Gabriel Moruz, Andrei Negoescu |
| 2012 | Computing the distance between piecewise-linear bivariate functions. | Guillaume Moroz, Boris Aronov |
| 2012 | Simultaneous approximations for adversarial and stochastic online budgeted allocation. | Vahab S. Mirrokni, Shayan Oveis Gharan, Morteza Zadimoghaddam |
| 2012 | The shifting sands algorithm. | Andrew McGregor, Paul Valiant |
| 2012 | Concentration inequalities for nonlinear matroid intersection. | Konstantin Makarychev, Warren Schudy, Maxim Sviridenko |
| 2012 | Stochastic coalescence in logarithmic time. | Po-Shen Loh, Eyal Lubetzky |
| 2012 | Approximate counting via correlation decay in spin systems. | Liang Li, Pinyan Lu, Yitong Yin |
| 2012 | Sequential auctions and externalities. | Renato Paes Leme, Vasilis Syrgkanis, va Tardos |
| 2012 | A new approach to the orientation of random hypergraphs. | Marc Lelarge |
| 2012 | Dimension reduction for finite trees in | James R. Lee, Arnaud de Mesmay, Mohammad Moharrami |
| 2012 | I/O-efficient data structures for colored range and prefix reporting. | Kasper Green Larsen, Rasmus Pagh |
| 2012 | Information dissemination via random walks in | Henry Lam, Zhenming Liu, Michael Mitzenmacher, Xiaorui Sun, Yajun Wang |
| 2012 | On the (in)security of hash-based oblivious RAM and a new balancing scheme. | Eyal Kushilevitz, Steve Lu, Rafail Ostrovsky |
| 2012 | Constant factor approximation algorithm for the knapsack median problem. | Amit Kumar |
| 2012 | Inapproximability of the multi-level uncapacitated facility location problem. | Ravishankar Krishnaswamy, Maxim Sviridenko |
| 2012 | Directed nowhere dense classes of graphs. | Stephan Kreutzer, Siamak Tazari |
| 2012 | Compression via matroids: a randomized polynomial kernel for odd cycle transversal. | Stefan Kratsch, Magnus Wahlstrm |
| 2012 | Co-nondeterminism in compositions: a kernelization lower bound for a Ramsey-type problem. | Stefan Kratsch |
| 2012 | The complexity of conservative valued CSPs. | Vladimir Kolmogorov, Stanislav Zivn |
| 2012 | Approximate duality of multicommodity multiroute flows and cuts: single source case. | Petr Kolman, Christian Scheideler |
| 2012 | A linear time algorithm for seeds computation. | Tomasz Kociumaka, Marcin Kubica, Jakub Radoszewski, Wojciech Rytter, Tomasz Walen |
| 2012 | Spanning closed walks and TSP in 3-connected planar graphs. | Ken-ichi Kawarabayashi, Kenta Ozeki |
| 2012 | List-coloring graphs without subdivisions and without immersions. | Ken-ichi Kawarabayashi, Yusuke Kobayashi |