| 2012 | Polynomial-Time Algorithms for Energy Games with Special Weight Structures. | Krishnendu Chatterjee, Monika Henzinger, Sebastian Krinninger, Danupon Nanongkai |
| 2012 | Optimal Lower Bound for Differentially Private Multi-party Aggregation. | T.-H. Hubert Chan, Elaine Shi, Dawn Song |
| 2012 | A Model for Minimizing Active Processor Time. | Jessica Chang, Harold N. Gabow, Samir Khuller |
| 2012 | Optimizing Social Welfare for Network Bargaining Games in the Face of Unstability, Greed and Spite. | T.-H. Hubert Chan, Fei Chen, Li Ning |
| 2012 | Revenue Guarantees in Sponsored Search Auctions. | Ioannis Caragiannis, Christos Kaklamanis, Panagiotis Kanellopoulos, Maria Kyropoulou |
| 2012 | The Clique Problem in Ray Intersection Graphs. | Sergio Cabello, Jean Cardinal, Stefan Langerman |
| 2012 | Locally Correct Frchet Matchings. | Kevin Buchin, Maike Buchin, Wouter Meulemans, Bettina Speckmann |
| 2012 | Two Dimensional Range Minimum Queries and Fibonacci Lattices. | Gerth Stlting Brodal, Pooya Davoodi, Moshe Lewenstein, Rajeev Raman, S. Srinivasa Rao |
| 2012 | The Stretch Factor of L 1- and L ∞ -Delaunay Triangulations. | Nicolas Bonichon, Cyril Gavoille, Nicolas Hanusse, Ljubomir Perkovic |
| 2012 | The Simplex Tree: An Efficient Data Structure for General Simplicial Complexes. | Jean-Daniel Boissonnat, Clment Maria |
| 2012 | Kinetic Compressed Quadtrees in the Black-Box Model with Applications to Collision Detection for Low-Density Scenes. | Mark de Berg, Marcel Roeloffzen, Bettina Speckmann |
| 2012 | Span Programs and Quantum Algorithms for st-Connectivity and Claw Detection. | Aleksandrs Belovs, Ben W. Reichardt |
| 2012 | New Lower and Upper Bounds for Representing Sequences. | Djamal Belazzougui, Gonzalo Navarro |
| 2012 | Time-Dependent Route Planning with Generalized Objective Functions. | Gernot Veit Batz, Peter Sanders |
| 2012 | A Bicriteria Approximation for the Reordering Buffer Problem. | Siddharth Barman, Shuchi Chawla, Seeun Umboh |
| 2012 | Weighted Geometric Set Multi-cover via Quasi-uniform Sampling. | Nikhil Bansal, Kirk Pruhs |
| 2012 | A 5-Approximation for Capacitated Facility Location. | Manisha Bansal, Naveen Garg, Neelima Gupta |
| 2012 | On Online Labeling with Polynomially Many Labels. | Martin Babka, Jan Bulnek, Vladimr Cunt, Michal Kouck, Michael E. Saks |
| 2012 | Explicit and Efficient Hash Families Suffice for Cuckoo Hashing with a Stash. | Martin Aumller, Martin Dietzfelbinger, Philipp Woelfel |
| 2012 | Simplifying Massive Contour Maps. | Lars Arge, Lasse Deleuran, Thomas Mlhave, Morten Revsbk, Jakob Truelsen |
| 2012 | On the Value of Job Migration in Online Makespan Minimization. | Susanne Albers, Matthias Hellwig |
| 2012 | I/O-efficient Hierarchical Diameter Approximation. | Deepak Ajwani, Ulrich Meyer, David Veith |
| 2012 | Constructing Street Networks from GPS Trajectories. | Mahmuda Ahmed, Carola Wenk |
| 2012 | Lower Bounds for Sorted Geometric Queries in the I/O Model. | Peyman Afshani, Norbert Zeh |
| 2012 | Bottleneck Non-crossing Matching in the Plane. | A. Karim Abu-Affash, Paz Carmi, Matthew J. Katz, Yohai Trabelsi |