| 2012 | Stochastic Matching with Commitment. | Kevin P. Costello, Prasad Tetali, Pushkar Tripathi |
| 2012 | Directed Subset Feedback Vertex Set Is Fixed-Parameter Tractable. | Rajesh Hemant Chitnis, Marek Cygan, Mohammad Taghi Hajiaghayi, Dniel Marx |
| 2012 | Computational Complexity of Traffic Hijacking under BGP and S-BGP. | Marco Chiesa, Giuseppe Di Battista, Thomas Erlebach, Maurizio Patrignani |
| 2012 | Computing the Visibility Polygon of an Island in a Polygonal Domain. | Danny Z. Chen, Haitao Wang |
| 2012 | Incentive Ratios of Fisher Markets. | Ning Chen, Xiaotie Deng, Hongyang Zhang, Jie Zhang |
| 2012 | Node-Weighted Network Design in Planar and Minor-Closed Families of Graphs. | Chandra Chekuri, Alina Ene, Ali Vakilian |
| 2012 | A Dependent LP-Rounding Approach for the k-Median Problem. | Moses Charikar, Shi Li |
| 2012 | Sparse Fault-Tolerant Spanners for Doubling Metrics with Bounded Hop-Diameter or Degree. | T.-H. Hubert Chan, Mingfei Li, Li Ning |
| 2012 | Edge Fault Tolerance on Sparse Networks. | Nishanth Chandran, Juan A. Garay, Rafail Ostrovsky |
| 2012 | Testing Coverage Functions. | Deeparnab Chakrabarty, Zhiyi Huang |
| 2012 | Improved LP-Rounding Approximation Algorithm for k-level Uncapacitated Facility Location. | Jaroslaw Byrka, Bartosz Rybicki |
| 2012 | Approximation Algorithms for Online Weighted Rank Function Maximization under Matroid Constraints. | Niv Buchbinder, Joseph Naor, R. Ravi, Mohit Singh |
| 2012 | A Saturation Method for Collapsible Pushdown Systems. | Christopher H. Broadbent, Arnaud Carayol, Matthew Hague, Olivier Serre |
| 2012 | Prefix Rewriting for Nested-Words and Collapsible Pushdown Automata. | Christopher H. Broadbent |
| 2012 | Efficient Sampling Methods for Discrete Distributions. | Karl Bringmann, Konstantinos Panagiotou |
| 2012 | Minimizing Expected Termination Time in One-Counter Markov Decision Processes. | Toms Brzdil, Antonn Kucera, Petr Novotn, Dominik Wojtczak |
| 2012 | Robust Reachability in Timed Automata: A Game-Based Approach. | Patricia Bouyer, Nicolas Markey, Ocan Sankur |
| 2012 | De-amortizing Binary Search Trees. | Prosenjit Bose, Sbastien Collette, Rolf Fagerberg, Stefan Langerman |
| 2012 | Toward Model Theory with Data Values. | Mikolaj Bojanczyk, Thomas Place |
| 2012 | Regular Languages of Infinite Trees That Are Boolean Combinations of Open Sets. | Mikolaj Bojanczyk, Thomas Place |
| 2012 | A Machine-Independent Characterization of Timed Languages. | Mikolaj Bojanczyk, Slawomir Lasota |
| 2012 | Preventing Unraveling in Social Networks: The Anchored k-Core Problem. | Kshipra Bhawalkar, Jon M. Kleinberg, Kevin Lewi, Tim Roughgarden, Aneesh Sharma |
| 2012 | On Quadratic Programming with a Ratio Objective. | Aditya Bhaskara, Moses Charikar, Rajsekar Manokaran, Aravindan Vijayaraghavan |
| 2012 | Super-Fast Distributed Algorithms for Metric Facility Location. | Andrew Berns, James Hegeman, Sriram V. Pemmaraju |
| 2012 | Monadic Datalog Containment. | Michael Benedikt, Pierre Bourhis, Pierre Senellart |