| 2012 | Optimizing Linear Functions with Randomized Search Heuristics - The Robustness of Mutation. | Carsten Witt |
| 2012 | A (k+3)/2-approximation algorithm for monotone submodular k-set packing and general k-exchange systems. | Justin Ward |
| 2012 | An Approximation Algorithm for #k-SAT. | Marc Thurley |
| 2012 | Randomized Communication Complexity for Linear Algebra Problems over Finite Fields. | Xiaoming Sun, Chengu Wang |
| 2012 | Iterative Methods in Combinatorial Optimization (Invited Talk). | R. Ravi |
| 2012 | A Pumping Lemma for Pushdown Graphs of Any Level. | Pawel Parys |
| 2012 | Simpler Approximation of the Maximum Asymmetric Traveling Salesman Problem. | Katarzyna E. Paluch, Khaled M. Elbassioni, Anke van Zuylen |
| 2012 | Efficiently Decodable Compressed Sensing by List-Recoverable Codes and Recursion. | Hung Q. Ngo, Ely Porat, Atri Rudra |
| 2012 | LP can be a cure for Parameterized Problems. | N. S. Narayanaswamy, Venkatesh Raman, M. S. Ramanujan, Saket Saurabh |
| 2012 | 13/9-approximation for Graphic TSP. | Marcin Mucha |
| 2012 | On the treewidth and related parameters of random geometric graphs. | Dieter Mitsche, Guillem Perarnau |
| 2012 | Constant compression and random weights. | Wolfgang Merkle, Jason Teutsch |
| 2012 | Improved Spectral Sparsification and Numerical Algorithms for SDD Matrices. | Ioannis Koutis, Alex Levin, Richard Peng |
| 2012 | Trichotomy for Integer Linear Systems Based on Their Sign Patterns. | Kei Kimura, Kazuhisa Makino |
| 2012 | Linear min-max relation between the treewidth of H-minor-free graphs and its largest grid. | Ken-ichi Kawarabayashi, Yusuke Kobayashi |
| 2012 | Edge-disjoint Odd Cycles in 4-edge-connected Graphs. | Ken-ichi Kawarabayashi, Yusuke Kobayashi |
| 2012 | Contraction checking in graphs on surfaces. | Marcin Kaminski, Dimitrios M. Thilikos |
| 2012 | Compressed Membership for NFA (DFA) with Compressed Labels is in NP (P). | Artur Jez |
| 2012 | Stronger Lower Bounds and Randomness-Hardness Trade-Offs Using Associated Algebraic Complexity Classes. | Maurice J. Jansen, Rahul Santhanam |
| 2012 | Mind Change Speed-up for Learning Languages from Positive Data. | Sanjay Jain, Efim B. Kinber |
| 2012 | Preemptive and Non-Preemptive Generalized Min Sum Set Cover. | Sungjin Im, Maxim Sviridenko, Ruben van der Zwaan |
| 2012 | The dimension of ergodic random sequences. | Mathieu Hoyrup |
| 2012 | Regular tree languages, cardinality predicates, and addition-invariant FO. | Frederik Harwath, Nicole Schweikardt |
| 2012 | Concurrency Makes Simple Theories Hard. | Stefan Gller, Anthony Widjaja Lin |
| 2012 | Pseudo-deterministic Algorithms (Invited Talk). | Shafi Goldwasser |