| 2012 | A faster algorithm to recognize even-hole-free graphs. Hsien-Chih Chang, Hsueh-I Lu |
| 2012 | A linear time algorithm for seeds computation. Tomasz Kociumaka, Marcin Kubica, Jakub Radoszewski, Wojciech Rytter, Tomasz Walen |
| 2012 | A little advice can be very helpful. Arkadev Chattopadhyay, Jeff Edmonds, Faith Ellen, Toniann Pitassi |
| 2012 | A matroid approach to stable matchings with lower quotas. Tamás Fleiner, Naoyuki Kamiyama |
| 2012 | A near-linear algorithm for projective clustering integer points. Kasturi R. Varadarajan, Xin Xiao |
| 2012 | A near-optimal sublinear-time algorithm for approximating the minimum vertex cover size. Krzysztof Onak, Dana Ron, Michal Rosen, Ronitt Rubinfeld |
| 2012 | A new approach to the orientation of random hypergraphs. Marc Lelarge |
| 2012 | A polynomial-time approximation scheme for planar multiway cut. MohammadHossein Bateni, MohammadTaghi Hajiaghayi, Philip N. Klein, Claire Mathieu |
| 2012 | A proof of the Boyd-Carr conjecture. Frans Schalekamp, David P. Williamson, Anke van Zuylen |
| 2012 | A satisfiability algorithm for AC Russell Impagliazzo, William Matthews, Ramamohan Paturi |
| 2012 | A scaling algorithm for maximum weight matching in bipartite graphs. Ran Duan, Hsin-Hao Su |
| 2012 | A simple algorithm for random colouring Charilaos Efthymiou |
| 2012 | A universally-truthful approximation scheme for multi-unit auctions. Berthold Vöcking |
| 2012 | Algorithms for the transportation problem in geometric settings. R. Sharathkumar, Pankaj K. Agarwal |
| 2012 | An Anna Adamaszek, Artur Czumaj, Matthias Englert, Harald Räcke |
| 2012 | An Krishnendu Chatterjee, Monika Henzinger |
| 2012 | An efficient polynomial-time approximation scheme for Steiner forest in planar graphs. David Eisenstat, Philip N. Klein, Claire Mathieu |
| 2012 | Analyzing graph structure via linear measurements. Kook Jin Ahn, Sudipto Guha, Andrew McGregor |
| 2012 | Approximate counting via correlation decay in spin systems. Liang Li, Pinyan Lu, Yitong Yin |
| 2012 | Approximate distance oracles with improved preprocessing time. Christian Wulff-Nilsen |
| 2012 | Approximate duality of multicommodity multiroute flows and cuts: single source case. Petr Kolman, Christian Scheideler |
| 2012 | Approximate tree decompositions of planar graphs in linear time. Frank Kammer, Torsten Tholey |
| 2012 | Approximating CSPs with global cardinality constraints using SDP hierarchies. Prasad Raghavendra, Ning Tan |
| 2012 | Approximating fixation probabilities in the generalized Moran process. Josep Díaz, Leslie Ann Goldberg, George B. Mertzios, David Richerby, Maria J. Serna, Paul G. Spirakis |
| 2012 | Approximating rooted Steiner networks. Joseph Cheriyan, Bundit Laekhanukit, Guyslain Naves, Adrian Vetta |
| 2012 | Approximation algorithms and hardness of the Julia Chuzhoy, Yury Makarychev, Aravindan Vijayaraghavan, Yuan Zhou |
| 2012 | Approximation algorithms for stochastic orienteering. Anupam Gupta, Ravishankar Krishnaswamy, Viswanath Nagarajan, R. Ravi |
| 2012 | Approximation algorithms for two-state anti-ferromagnetic spin systems on bounded degree graphs. Alistair Sinclair, Piyush Srivastava, Marc Thurley |
| 2012 | Beyond myopic best response (in Cournot competition). Amos Fiat, Elias Koutsoupias, Katrina Ligett, Yishay Mansour, Svetlana Olonetsky |
| 2012 | Bidimensionality and geometric graphs. Fedor V. Fomin, Daniel Lokshtanov, Saket Saurabh |
| 2012 | Black-box reductions for cost-sharing mechanism design. Konstantinos Georgiou, Chaitanya Swamy |
| 2012 | Bypassing UGC from some optimal geometric inapproximability results. Venkatesan Guruswami, Prasad Raghavendra, Rishi Saket, Yi Wu |
| 2012 | Co-nondeterminism in compositions: a kernelization lower bound for a Ramsey-type problem. Stefan Kratsch |
| 2012 | Competitive routing in the half-θ Prosenjit Bose, Rolf Fagerberg, André van Renssen, Sander Verdonschot |
| 2012 | Compression via matroids: a randomized polynomial kernel for odd cycle transversal. Stefan Kratsch, Magnus Wahlström |
| 2012 | Computing all maps into a sphere. Martin Cadek, Marek Krcál, Jirí Matousek, Francis Sergeraert, Lukás Vokrínek, Uli Wagner |
| 2012 | Computing the distance between piecewise-linear bivariate functions. Guillaume Moroz, Boris Aronov |
| 2012 | Concentration and moment inequalities for polynomials of independent random variables. Warren Schudy, Maxim Sviridenko |
| 2012 | Concentration inequalities for nonlinear matroid intersection. Konstantin Makarychev, Warren Schudy, Maxim Sviridenko |
| 2012 | Confluent persistence revisited. Sébastien Collette, John Iacono, Stefan Langerman |
| 2012 | Constant factor approximation algorithm for the knapsack median problem. Amit Kumar |
| 2012 | Constructing high order elements through subspace polynomials. Qi Cheng, Shuhong Gao, Daqing Wan |
| 2012 | Counting perfect matchings as fast as Ryser. Andreas Björklund |
| 2012 | Data reduction for weighted and outlier-resistant clustering. Dan Feldman, Leonard J. Schulman |
| 2012 | Deterministic construction of an approximate M-ellipsoid and its applications to derandomizing lattice algorithms. Daniel Dadush, Santosh S. Vempala |
| 2012 | Dimension reduction for finite trees in James R. Lee, Arnaud de Mesmay, Mohammad Moharrami |
| 2012 | Directed nowhere dense classes of graphs. Stephan Kreutzer, Siamak Tazari |
| 2012 | Efficient algorithms for maximum weight matchings in general graphs with small edge weights. Chien-Chung Huang, Telikepalli Kavitha |
| 2012 | Erdös-Pósa property and its algorithmic applications: parity constraints, subset feedback set, and subset packing. Naonori Kakimura, Ken-ichi Kawarabayashi, Yusuke Kobayashi |
| 2012 | Exact distance oracles for planar graphs. Shay Mozes, Christian Sommer |
| 2012 | Expanders are universal for the class of all spanning trees. Daniel Johannsen, Michael Krivelevich, Wojciech Samotij |
| 2012 | Fast zeta transforms for lattices with few irreducibles. Andreas Björklund, Mikko Koivisto, Thore Husfeldt, Jesper Nederlof, Petteri Kaski, Pekka Parviainen |
| 2012 | Finding an induced path of given parity in planar graphs in polynomial time. Marcin Kaminski, Naomi Nishimura |
| 2012 | Fixed-parameter tractability of directed multiway cut parameterized by the size of the cutset. Rajesh Hemant Chitnis, MohammadTaghi Hajiaghayi, Dániel Marx |
| 2012 | Fully persistent B-trees. Gerth Stølting Brodal, Konstantinos Tsakalidis, Spyros Sioutas, Kostas Tsichlas |
| 2012 | Gathering despite mischief. Yoann Dieudonné, Andrzej Pelc, David Peleg |
| 2012 | Global minimum cuts in surface embedded graphs. Jeff Erickson, Kyle Fox, Amir Nayyeri |
| 2012 | I/O-efficient data structures for colored range and prefix reporting. Kasper Green Larsen, Rasmus Pagh |
| 2012 | Improved competitive ratio for the matroid secretary problem. Sourav Chakraborty, Oded Lachish |
| 2012 | Improved output-sensitive quantum algorithms for Boolean matrix multiplication. François Le Gall |
| 2012 | Inapproximability of the multi-level uncapacitated facility location problem. Ravishankar Krishnaswamy, Maxim Sviridenko |
| 2012 | Information dissemination via random walks in Henry Lam, Zhenming Liu, Michael Mitzenmacher, Xiaorui Sun, Yajun Wang |
| 2012 | Jaywalking your dog: computing the Fréchet distance with shortcuts. Anne Driemel, Sariel Har-Peled |
| 2012 | Kernelization of packing problems. Holger Dell, Dániel Marx |
| 2012 | LSH-preserving functions and their applications. Flavio Chierichetti, Ravi Kumar |
| 2012 | Learning Constantinos Daskalakis, Ilias Diakonikolas, Rocco A. Servedio |
| 2012 | Linear index coding via semidefinite programming. Eden Chlamtac, Ishay Haviv |
| 2012 | Linear kernels for (connected) dominating set on Fedor V. Fomin, Daniel Lokshtanov, Saket Saurabh, Dimitrios M. Thilikos |
| 2012 | List-coloring graphs without subdivisions and without immersions. Ken-ichi Kawarabayashi, Yusuke Kobayashi |
| 2012 | Local homology transfer and stratification learning. Paul Bendich, Bei Wang, Sayan Mukherjee |
| 2012 | Lower bounds for number-in-hand multiparty communication complexity, made easy. Jeff M. Phillips, Elad Verbin, Qin Zhang |
| 2012 | Matroidal degree-bounded minimum spanning trees. Rico Zenklusen |
| 2012 | Mechanism design via consensus estimates, cross checking, and profit extraction. Bach Q. Ha, Jason D. Hartline |
| 2012 | Metastability of logit dynamics for coordination games. Vincenzo Auletta, Diodato Ferraioli, Francesco Pasquale, Giuseppe Persiano |
| 2012 | Near linear time (1 + ε)-approximation for restricted shortest paths in undirected graphs. Aaron Bernstein |
| 2012 | Networks cannot compute their diameter in sublinear time. Silvio Frischknecht, Stephan Holzer, Roger Wattenhofer |
| 2012 | On a linear program for minimum-weight triangulation. Arman Yousefi, Neal E. Young |
| 2012 | On multiplicative λ-approximations and some geometric applications. Ilan Newman, Yuri Rabinovich |
| 2012 | On the (in)security of hash-based oblivious RAM and a new balancing scheme. Eyal Kushilevitz, Steve Lu, Rafail Ostrovsky |
| 2012 | On the communication and streaming complexity of maximum bipartite matching. Ashish Goel, Michael Kapralov, Sanjeev Khanna |
| 2012 | On the hardness of pricing loss-leaders. Preyas Popat, Yi Wu |
| 2012 | Online scheduling with general cost functions. Sungjin Im, Benjamin Moseley, Kirk Pruhs |
| 2012 | Optimal column-based low-rank matrix reconstruction. Venkatesan Guruswami, Ali Kemal Sinop |
| 2012 | Optimal crowdsourcing contests. Shuchi Chawla, Jason D. Hartline, Balasubramanian Sivan |
| 2012 | Outperforming LRU via competitive analysis on parametrized inputs for paging. Gabriel Moruz, Andrei Negoescu |
| 2012 | Packing anchored rectangles. Adrian Dumitrescu, Csaba D. Tóth |
| 2012 | Parallelism and time in hierarchical self-assembly. Ho-Lin Chen, David Doty |
| 2012 | Partial match queries in random quadtrees. Nicolas Broutin, Ralph Neininger, Henning Sulzbach |
| 2012 | Physarum can compute shortest paths. Vincenzo Bonifaci, Kurt Mehlhorn, Girish Varma |
| 2012 | Polynomial integrality gaps for strong SDP relaxations of Densest Aditya Bhaskara, Moses Charikar, Aravindan Vijayaraghavan, Venkatesan Guruswami, Yuan Zhou |
| 2012 | Polytope approximation and the Mahler volume. Sunil Arya, Guilherme Dias da Fonseca, David M. Mount |
| 2012 | Popularity vs maximum cardinality in the stable marriage setting. Telikepalli Kavitha |
| 2012 | Privacy-preserving group data access via stateless oblivious RAM simulation. Michael T. Goodrich, Michael Mitzenmacher, Olga Ohrimenko, Roberto Tamassia |
| 2012 | Private data release via learning thresholds. Moritz Hardt, Guy N. Rothblum, Rocco A. Servedio |
| 2012 | Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2012, Kyoto, Japan, January 17-19, 2012 Yuval Rabani |
| 2012 | Race to idle: new algorithms for speed scaling with a sleep state. Susanne Albers, Antonios Antoniadis |
| 2012 | Random walks, electric networks and the transience class problem of sandpiles. Ayush Choure, Sundar Vishwanathan |
| 2012 | Resource augmentation for weighted flow-time explained by dual fitting. S. Anand, Naveen Garg, Amit Kumar |
| 2012 | Rumor spreading and vertex expansion. George Giakkoupis, Thomas Sauerwald |
| 2012 | SINR diagram with interference cancellation. Chen Avin, Asaf Cohen, Yoram Haddad, Erez Kantor, Zvi Lotker, Merav Parter, David Peleg |
| 2012 | Scheduling heterogeneous processors isn't as easy as you think. Anupam Gupta, Sungjin Im, Ravishankar Krishnaswamy, Benjamin Moseley, Kirk Pruhs |
| 2012 | Separating stable sets in claw-free graphs via Padberg-Rao and compact linear programs. Yuri Faenza, Gianpaolo Oriolo, Gautier Stauffer |
| 2012 | Sequential auctions and externalities. Renato Paes Leme, Vasilis Syrgkanis, Éva Tardos |
| 2012 | Shortest cycle through specified elements. Andreas Björklund, Thore Husfeldt, Nina Taslaman |
| 2012 | Simple and practical algorithm for sparse Fourier transform. Haitham Hassanieh, Piotr Indyk, Dina Katabi, Eric Price |
| 2012 | Simultaneous approximations for adversarial and stochastic online budgeted allocation. Vahab S. Mirrokni, Shayan Oveis Gharan, Morteza Zadimoghaddam |
| 2012 | Single source distance oracle for planar digraphs avoiding a failed node or link. Surender Baswana, Utkarsh Lath, Anuradha S. Mehta |
| 2012 | Sketching valuation functions. Ashwinkumar Badanidiyuru, Shahar Dobzinski, Hu Fu, Robert Kleinberg, Noam Nisan, Tim Roughgarden |
| 2012 | Space-efficient local computation algorithms. Noga Alon, Ronitt Rubinfeld, Shai Vardi, Ning Xie |
| 2012 | Spanning closed walks and TSP in 3-connected planar graphs. Ken-ichi Kawarabayashi, Kenta Ozeki |
| 2012 | Sparser Johnson-Lindenstrauss transforms. Daniel M. Kane, Jelani Nelson |
| 2012 | Stochastic coalescence in logarithmic time. Po-Shen Loh, Eyal Lubetzky |
| 2012 | Structural and logical approaches to the graph isomorphism problem. Martin Grohe |
| 2012 | Subexponential parameterized algorithm for minimum fill-in. Fedor V. Fomin, Yngve Villanger |
| 2012 | Sublinear time, measurement-optimal, sparse recovery for all. Ely Porat, Martin J. Strauss |
| 2012 | Submatrix maximum queries in Monge matrices and Monge partial matrices, and their applications. Haim Kaplan, Shay Mozes, Yahav Nussbaum, Micha Sharir |
| 2012 | Submodular functions are noise stable. Mahdi Cheraghchi, Adam R. Klivans, Pravesh Kothari, Homin K. Lee |
| 2012 | Subquadratic time approximation algorithms for the girth. Liam Roditty, Virginia Vassilevska Williams |
| 2012 | Testing odd-cycle-freeness in Boolean functions. Arnab Bhattacharyya, Elena Grigorescu, Prasad Raghavendra, Asaf Shapira |
| 2012 | The MAX-CUT of sparse random graphs. Hervé Daudé, Conrado Martínez, Vonjy Rasendrahasina, Vlady Ravelomanana |
| 2012 | The complexity of conservative valued CSPs. Vladimir Kolmogorov, Stanislav Zivný |
| 2012 | The condensation transition in random hypergraph 2-coloring. Amin Coja-Oghlan, Lenka Zdeborová |
| 2012 | The entropy rounding method in approximation algorithms. Thomas Rothvoß |
| 2012 | The maximum degree of random planar graphs. Michael Drmota, Omer Giménez, Marc Noy, Konstantinos Panagiotou, Angelika Steger |
| 2012 | The maximum number of faces of the Minkowski sum of two convex polytopes. Menelaos I. Karavelas, Eleni Tzanaki |
| 2012 | The mixing time of the Newman: Watts small world. Louigi Addario-Berry, Tao Lei |
| 2012 | The notion of a rational convex program, and an algorithm for the Arrow-Debreu Nash bargaining game. Vijay V. Vazirani |
| 2012 | The set of solutions of random XORSAT formulae. Morteza Ibrahimi, Yashodhan Kanoria, Matt Kraning, Andrea Montanari |
| 2012 | The shifting sands algorithm. Andrew McGregor, Paul Valiant |
| 2012 | Tight bounds on the maximum size of a set of permutations with bounded VC-dimension. Josef Cibulka, Jan Kyncl |
| 2012 | Top- Gonzalo Navarro, Yakov Nekrich |
| 2012 | Towards robust and efficient computation in dynamic peer-to-peer networks. John Augustine, Gopal Pandurangan, Peter Robinson, Eli Upfal |
| 2012 | Traffic-redundancy aware network design. Siddharth Barman, Shuchi Chawla |
| 2012 | Ultra-fast rumor spreading in social networks. Nikolaos Fountoulakis, Konstantinos Panagiotou, Thomas Sauerwald |
| 2012 | Using hashing to solve the dictionary problem. John Iacono, Mihai Patrascu |
| 2012 | Voting with limited information and many alternatives. Flavio Chierichetti, Jon M. Kleinberg |
| 2012 | Weak compositions and their applications to polynomial lower bounds for kernelization. Danny Hermelin, Xi Wu |
| 2012 | Weighted capacitated, priority, and geometric set cover via improved quasi-uniform sampling. Timothy M. Chan, Elyot Grant, Jochen Könemann, Malcolm Sharpe |
| 2012 | Width of points in the streaming model. Alexandr Andoni, Huy L. Nguyen |
| 2012 | Wireless connectivity and capacity. Magnús M. Halldórsson, Pradipta Mitra |