| 2012 | An Automata-Theoretic Model of Idealized Algol - (Extended Abstract). | Uday S. Reddy, Brian P. Dunphy |
| 2012 | Strictly-Black-Box Zero-Knowledge and Efficient Validation of Financial Transactions. | Michael O. Rabin, Yishay Mansour, S. Muthukrishnan, Moti Yung |
| 2012 | Quasi-polynomial Local Search for Restricted Max-Min Fair Allocation. | Lukas Polacek, Ola Svensson |
| 2012 | Distributed Algorithms for Network Diameter and Girth. | David Peleg, Liam Roditty, Elad Tal |
| 2012 | Two-Level Game Semantics, Intersection Types, and Recursion Schemes. | C.-H. Luke Ong, Takeshi Tsukada |
| 2012 | Online Packing with Gradually Improving Capacity Estimations and Applications to Network Lifetime Maximization. | Marcel Ochel, Klaus Radke, Berthold Vcking |
| 2012 | Algorithmic Games for Full Ground References. | Andrzej S. Murawski, Nikos Tzevelekos |
| 2012 | Geometry of Online Packing Linear Programs. | Marco Molinaro, R. Ravi |
| 2012 | The Power of Recourse for Online MST and TSP. | Nicole Megow, Martin Skutella, Jos Verschae, Andreas Wiese |
| 2012 | A Tight Lower Bound for Planar Multiway Cut with Fixed Number of Terminals. | Dniel Marx |
| 2012 | Assigning Sporadic Tasks to Unrelated Parallel Machines. | Alberto Marchetti-Spaccamela, Cyriel Rutten, Suzanne van der Ster, Andreas Wiese |
| 2012 | Converting Online Algorithms to Local Computation Algorithms. | Yishay Mansour, Aviad Rubinstein, Shai Vardi, Ning Xie |
| 2012 | Parameterized Tractability of Multiway Cut with Parity Constraints. | Daniel Lokshtanov, M. S. Ramanujan |
| 2012 | Coalgebraic Predicate Logic. | Tadeusz Litak, Dirk Pattinson, Katsuhiko Sano, Lutz Schrder |
| 2012 | The Parameterized Complexity of k-Edge Induced Subgraphs. | Bingkai Lin, Yijia Chen |
| 2012 | Testing Similar Means. | Reut Levi, Dana Ron, Ronitt Rubinfeld |
| 2012 | Classical and Quantum Partition Bound and Detector Inefficiency. | Sophie Laplante, Virginie Lerays, Jrmie Roland |
| 2012 | A Rounding by Sampling Approach to the Minimum Size k-Arc Connected Subgraph Problem. | Bundit Laekhanukit, Shayan Oveis Gharan, Mohit Singh |
| 2012 | On the Expressive Power of Cost Logics over Infinite Words. | Denis Kuperberg, Michael Vanden Boom |
| 2012 | Lattices of Logical Fragments over Words - (Extended Abstract). | Manfred Kufleitner, Alexander Lauser |
| 2012 | Online Mechanism Design (Randomized Rounding on the Fly). | Piotr Krysta, Berthold Vcking |
| 2012 | Preserving Terminal Distances Using Minors. | Robert Krauthgamer, Tamar Zondiner |
| 2012 | Fixed-Parameter Tractability of Multicut in Directed Acyclic Graphs. | Stefan Kratsch, Marcin Pilipczuk, Michal Pilipczuk, Magnus Wahlstrm |
| 2012 | Contention Issues in Congestion Games. | Elias Koutsoupias, Katia Papakonstantinopoulou |
| 2012 | k-Chordal Graphs: From Cops and Robber to Compact Routing via Treewidth. | Adrian Kosowski, Bi Li, Nicolas Nisse, Karol Suchan |