| 2012 | A Better Approximation Ratio and an IP Formulation for a Sensor Cover Problem. Rafael da Ponte Barbosa, Yoshiko Wakabayashi |
| 2012 | A Generalization of the Convex Kakeya Problem. Hee-Kap Ahn, Sang Won Bae, Otfried Cheong, Joachim Gudmundsson, Takeshi Tokuyama, Antoine Vigneron |
| 2012 | A O(1/ε 2) n -Time Sieving Algorithm for Approximate Integer Programming. Daniel Dadush |
| 2012 | A Theory and Algorithms for Combinatorial Reoptimization. Hadas Shachnai, Gal Tamir, Tami Tamir |
| 2012 | Advantage of Overlapping Clusters for Minimizing Conductance. Rohit Khandekar, Guy Kortsarz, Vahab S. Mirrokni |
| 2012 | Algorithms for Some H-Join Decompositions. Michel Habib, Antoine Mamcarz, Fabien de Montgolfier |
| 2012 | An Equivariance Theorem with Applications to Renaming. Armando Castañeda, Maurice Herlihy, Sergio Rajsbaum |
| 2012 | An Improved Upper Bound on the Density of Universal Random Graphs. Domingos Dellamonica Jr., Yoshiharu Kohayakawa, Vojtech Rödl, Andrzej Rucinski |
| 2012 | Approximating Minimum Label s-t Cut via Linear Programming. Linqing Tang, Peng Zhang |
| 2012 | Approximating the Edge Length of 2-Edge Connected Planar Geometric Graphs on a Set of Points. Stefan Dobrev, Evangelos Kranakis, Danny Krizanc, Oscar Morales-Ponce, Ladislav Stacho |
| 2012 | Bichromatic 2-Center of Pairs of Points. Esther M. Arkin, José Miguel Díaz-Báñez, Ferran Hurtado, Piyush Kumar, Joseph S. B. Mitchell, Belén Palop, Pablo Pérez-Lantero, Maria Saumell, Rodrigo I. Silveira |
| 2012 | Cache Me If You Can: Capacitated Selfish Replication Games. Ragavendran Gopalakrishnan, Dimitrios Kanoulas, Naga Naresh Karuturi, C. Pandu Rangan, Rajmohan Rajaraman, Ravi Sundaram |
| 2012 | Capacity Achieving Two-Write WOM Codes. Amir Shpilka |
| 2012 | Clique-Colouring and Biclique-Colouring Unichord-Free Graphs. Hélio B. Macêdo Filho, Raphael C. S. Machado, Celina M. H. de Figueiredo |
| 2012 | Coloring Planar Homothets and Three-Dimensional Hypergraphs. Jean Cardinal, Matias Korman |
| 2012 | Computing Minimum Geodetic Sets of Proper Interval Graphs. Tínaz Ekim, Aysel Erey, Pinar Heggernes, Pim van 't Hof, Daniel Meister |
| 2012 | Decidability Classes for Mobile Agents Computing. Pierre Fraigniaud, Andrzej Pelc |
| 2012 | Degree-Constrained Node-Connectivity. Zeev Nutov |
| 2012 | Density Classification on Infinite Lattices and Trees. Ana Busic, Nazim Fatès, Jean Mairesse, Irène Marcovici |
| 2012 | Efficient Arbitrary and Resolution Proofs of Unsatisfiability for Restricted Tree-Width. Martin Fürer |
| 2012 | Erdős-Rényi Sequences and Deterministic Construction of Expanding Cayley Graphs. Vikraman Arvind, Partha Mukhopadhyay, Prajakta Nimbhorkar |
| 2012 | Forbidden Patterns. Johannes Fischer, Travis Gagie, Tsvi Kopelowitz, Moshe Lewenstein, Veli Mäkinen, Leena Salmela, Niko Välimäki |
| 2012 | Fully Analyzing an Algebraic Pólya Urn Model. Basile Morcrette |
| 2012 | Hausdorff Rank of Scattered Context-Free Linear Orders. Zoltán Ésik, Szabolcs Iván |
| 2012 | Hiring above the m-th Best Candidate: A Generalization of Records in Permutations. Ahmed Helmi, Conrado Martínez, Alois Panholzer |
| 2012 | Independence of Tabulation-Based Hash Classes. Toryn Qwyllyn Klassen, Philipp Woelfel |
| 2012 | Indexed Multi-pattern Matching. Travis Gagie, Kalle Karhu, Juha Kärkkäinen, Veli Mäkinen, Leena Salmela, Jorma Tarhio |
| 2012 | LATIN 2012: Theoretical Informatics - 10th Latin American Symposium, Arequipa, Peru, April 16-20, 2012. Proceedings David Fernández-Baca |
| 2012 | Logspace Computations in Graph Groups and Coxeter Groups. Volker Diekert, Jonathan Kausch, Markus Lohrey |
| 2012 | Low Complexity Scheduling Algorithm Minimizing the Energy for Tasks with Agreeable Deadlines. Eric Angel, Evripidis Bampis, Vincent Chau |
| 2012 | NE Is Not NP Turing Reducible to Nonexponentially Dense NP Sets. Bin Fu |
| 2012 | New Lower Bound on Max Cut of Hypergraphs with an Application to r -Set Splitting. Archontia C. Giannopoulou, Sudeshna Kolay, Saket Saurabh |
| 2012 | Oblivious Two-Way Finite Automata: Decidability and Complexity. Martin Kutrib, Andreas Malcher, Giovanni Pighizzini |
| 2012 | On Plane Constrained Bounded-Degree Spanners. Prosenjit Bose, Rolf Fagerberg, André van Renssen, Sander Verdonschot |
| 2012 | On the Advice Complexity of the Knapsack Problem. Hans-Joachim Böckenhauer, Dennis Komm, Richard Královic, Peter Rossmanith |
| 2012 | On the Bend-Number of Planar and Outerplanar Graphs. Daniel Heldt, Kolja B. Knauer, Torsten Ueckerdt |
| 2012 | On the Integrality Gap of the Subtour LP for the 1, 2-TSP. Jiawei Qian, Frans Schalekamp, David P. Williamson, Anke van Zuylen |
| 2012 | On the Non-progressive Spread of Influence through Social Networks. MohammadAmin Fazli, Mohammad Ghodsi, Jafar Habibi, Pooya Jalaly Khalilabadi, Vahab S. Mirrokni, Sina Sadeghian Sadeghabad |
| 2012 | On the Performance of Smith's Rule in Single-Machine Scheduling with Nonlinear Cost. Wiebke Höhn, Tobias Jacobs |
| 2012 | On the Radon Number for P 3-Convexity. Mitre Costa Dourado, Dieter Rautenbach, Vinícius Fernandes dos Santos, Philipp Matthias Schäfer, Jayme Luiz Szwarcfiter, Alexandre Toman |
| 2012 | Opportunistic Information Dissemination in Mobile Ad-Hoc Networks: Adaptiveness vs. Obliviousness and Randomization vs. Determinism. Martin Farach-Colton, Antonio Fernández Anta, Alessia Milani, Miguel A. Mosteiro, Shmuel Zaks |
| 2012 | Parameterized Complexity of MaxSat above Average. Robert Crowston, Gregory Z. Gutin, Mark Jones, Venkatesh Raman, Saket Saurabh |
| 2012 | Pseudorandomness of a Random Kronecker Sequence. Eda Cesaratto, Brigitte Vallée |
| 2012 | Random Walks and Bisections in Random Circulant Graphs. Bernard Mans, Igor E. Shparlinski |
| 2012 | Renaming Is Weaker Than Set Agreement But for Perfect Renaming: A Map of Sub-consensus Tasks. Armando Castañeda, Damien Imbs, Sergio Rajsbaum, Michel Raynal |
| 2012 | Reoptimization of Some Maximum Weight Induced Hereditary Subgraph Problems. Nicolas Boria, Jérôme Monnot, Vangelis Th. Paschos |
| 2012 | Revisiting the Cache Miss Analysis of Multithreaded Algorithms. Richard Cole, Vijaya Ramachandran |
| 2012 | Solving the 2-Disjoint Connected Subgraphs Problem Faster Than 2 n. Marek Cygan, Marcin Pilipczuk, Michal Pilipczuk, Jakub Onufry Wojtaszczyk |
| 2012 | Space-Efficient Approximation Scheme for Circular Earth Mover Distance. Joshua Brody, Hongyu Liang, Xiaoming Sun |
| 2012 | Structural Complexity of Multiobjective NP Search Problems. Krzysztof Fleszar, Christian Glaßer, Fabian Lipp, Christian Reitwießner, Maximilian Witek |
| 2012 | Survivable Network Activation Problems. Zeev Nutov |
| 2012 | The Efficiency of MapReduce in Parallel External Memory. Gero Greiner, Riko Jacob |
| 2012 | The Feedback Arc Set Problem with Triangle Inequality Is a Vertex Cover Problem. Monaldo Mastrolilli |
| 2012 | The Relationship between Inner Product and Counting Cycles. Xiaoming Sun, Chengu Wang, Wei Yu |
| 2012 | Two-Dimensional Range Diameter Queries. Pooya Davoodi, Michiel H. M. Smid, Freek van Walderveen |
| 2012 | k-Gap Interval Graphs. Fedor V. Fomin, Serge Gaspers, Petr A. Golovach, Karol Suchan, Stefan Szeider, Erik Jan van Leeuwen, Martin Vatshelle, Yngve Villanger |