| 2009 | (Un)expected behavior of digital search tree profile. Michael Drmota, Wojciech Szpankowski |
| 2009 | 3-bit dictator testing: 1 vs. 5/8. Ryan O'Donnell, Yi Wu |
| 2009 | A generic top-down dynamic-programming approach to prefix-free coding. Mordecai J. Golin, Xiaoming Xu, Jiajin Yu |
| 2009 | A logarithmic approximation for unsplittable flow on line graphs. Nikhil Bansal, Zachary Friggstad, Rohit Khandekar, Mohammad R. Salavatipour |
| 2009 | A near-linear time algorithm for constructing a cactus representation of minimum cuts. David R. Karger, Debmalya Panigrahi |
| 2009 | A nearly linear time algorithm for the half integral parity disjoint paths packing problem. Ken-ichi Kawarabayashi, Bruce A. Reed |
| 2009 | A new approach to incremental topological ordering. Michael A. Bender, Jeremy T. Fineman, Seth Gilbert |
| 2009 | A quadratic kernel for feedback vertex set. Stéphan Thomassé |
| 2009 | A simple combinatorial algorithm for submodular function minimization. Satoru Iwata, James B. Orlin |
| 2009 | A simpler implementation and analysis of Chazelle's soft heaps. Haim Kaplan, Uri Zwick |
| 2009 | A unified approach to distance-two colouring of planar graphs. Omid Amini, Louis Esperet, Jan van den Heuvel |
| 2009 | A universally fastest algorithm for Max 2-Sat, Max 2-CSP, and everything in between. Serge Gaspers, Gregory B. Sorkin |
| 2009 | Additive approximation algorithms for list-coloring minor-closed class of graphs. Ken-ichi Kawarabayashi, Erik D. Demaine, MohammadTaghi Hajiaghayi |
| 2009 | Algorithms for finding an induced cycle in planar graphs and bounded genus graphs. Yusuke Kobayashi, Ken-ichi Kawarabayashi |
| 2009 | Almost all hypergraphs without Fano planes are bipartite. Yury Person, Mathias Schacht |
| 2009 | An almost Zeev Nutov |
| 2009 | An efficient sparse regularity concept. Amin Coja-Oghlan, Colin Cooper, Alan M. Frieze |
| 2009 | An improved approximation algorithm for the column subset selection problem. Christos Boutsidis, Michael W. Mahoney, Petros Drineas |
| 2009 | An online mechanism for ad slot reservations with cancellations. Florin Constantin, Jon Feldman, S. Muthukrishnan, Martin Pál |
| 2009 | Analysis of scalar fields over point cloud data. Frédéric Chazal, Leonidas J. Guibas, Steve Oudot, Primoz Skraba |
| 2009 | Appointment scheduling with discrete random durations. Mehmet A. Begen, Maurice Queyranne |
| 2009 | Approximate Euclidean shortest paths amid convex obstacles. Pankaj K. Agarwal, R. Sharathkumar, Hai Yu |
| 2009 | Approximate clustering without the approximation. Maria-Florina Balcan, Avrim Blum, Anupam Gupta |
| 2009 | Approximate line nearest neighbor in high dimensions. Alexandr Andoni, Piotr Indyk, Robert Krauthgamer, Huy L. Nguyen |
| 2009 | Approximate shared-memory counting despite a strong adversary. James Aspnes, Keren Censor |
| 2009 | Approximating fractional hypertree width. Dániel Marx |
| 2009 | Approximating submodular functions everywhere. Michel X. Goemans, Nicholas J. A. Harvey, Satoru Iwata, Vahab S. Mirrokni |
| 2009 | Approximation algorithms for restless bandit problems. Sudipto Guha, Kamesh Munagala, Peng Shi |
| 2009 | Assignment problem in content distribution networks: unsplittable hard-capacitated facility location. MohammadHossein Bateni, MohammadTaghi Hajiaghayi |
| 2009 | Asymptotically optimal frugal colouring. Michael Molloy, Bruce A. Reed |
| 2009 | Better algorithms for benign bandits. Elad Hazan, Satyen Kale |
| 2009 | Biased range trees. Vida Dujmovic, John Howat, Pat Morin |
| 2009 | Cell probe lower bounds for succinct data structures. Alexander Golynski |
| 2009 | Clique-width: on the price of generality. Fedor V. Fomin, Petr A. Golovach, Daniel Lokshtanov, Saket Saurabh |
| 2009 | Collecting weighted items from a dynamic queue. Marcin Bienkowski, Marek Chrobak, Christoph Dürr, Mathilde Hurand, Artur Jez, Lukasz Jez, Grzegorz Stachowiak |
| 2009 | Coloring triangle-free graphs on surfaces. Zdenek Dvorák, Daniel Král, Robin Thomas |
| 2009 | Column subset selection, matrix factorization, and eigenvalue optimization. Joel A. Tropp |
| 2009 | Combinatorial algorithms for nearest neighbors, near-duplicates and small-world design. Yury Lifshits, Shengyu Zhang |
| 2009 | Combinatorial algorithms for wireless information flow. Aurore Amaudruz, Christina Fragouli |
| 2009 | Combinatorial stochastic processes and nonparametric Bayesian modeling. Michael I. Jordan |
| 2009 | Comparison-based time-space lower bounds for selection. Timothy M. Chan |
| 2009 | Compressed counting. Ping Li |
| 2009 | Computing the nucleolus of weighted voting games. Edith Elkind, Dmitrii V. Pasechnik |
| 2009 | Constructing Laplace operator from point clouds in Mikhail Belkin, Jian Sun, Yusu Wang |
| 2009 | Coresets and approximate clustering for Bregman divergences. Marcel R. Ackermann, Johannes Blömer |
| 2009 | Decomposition of multiple coverings into more parts. Greg Aloupis, Jean Cardinal, Sébastien Collette, Stefan Langerman, David Orden, Pedro Ramos |
| 2009 | Dimension detection via slivers. Siu-Wing Cheng, Man-Kwun Chiu |
| 2009 | Discounted deterministic Markov decision processes and discounted all-pairs shortest paths. Omid Madani, Mikkel Thorup, Uri Zwick |
| 2009 | Dual-failure distance and connectivity oracles. Ran Duan, Seth Pettie |
| 2009 | Efficient algorithms for the 2-gathering problem. Alon Shalita, Uri Zwick |
| 2009 | Efficient algorithms on sets of permutations, dominance, and real-weighted APSP. Raphael Yuster |
| 2009 | Efficient coordination mechanisms for unrelated machine scheduling. Ioannis Caragiannis |
| 2009 | Equilibria of atomic flow games are not unique. Umang Bhaskar, Lisa Fleischer, Darrell Hoy, Chien-Chung Huang |
| 2009 | Exact algorithms for partial curve matching via the Fréchet distance. Kevin Buchin, Maike Buchin, Yusu Wang |
| 2009 | Expanders via random spanning trees. Navin Goyal, Luis Rademacher, Santosh S. Vempala |
| 2009 | Exponential lower bounds and integrality gaps for tree-like Lovász-Schrijver procedures. Toniann Pitassi, Nathan Segerlind |
| 2009 | Fast algorithms for (max, min)-matrix multiplication and bottleneck shortest paths. Ran Duan, Seth Pettie |
| 2009 | Fast edge orientation for unweighted graphs. Anand Bhalgat, Ramesh Hariharan |
| 2009 | Finding duplicates in a data stream. Parikshit Gopalan, Jaikumar Radhakrishnan |
| 2009 | Finding shortest contractible and shortest separating cycles in embedded graphs. Sergio Cabello |
| 2009 | From coding theory to efficient pattern matching. Raphaël Clifford, Klim Efremenko, Ely Porat, Amir Rothschild |
| 2009 | Generating random graphs with large girth. Mohsen Bayati, Andrea Montanari, Amin Saberi |
| 2009 | Hardness of embedding simplicial complexes in Jirí Matousek, Martin Tancer, Uli Wagner |
| 2009 | High rate fingerprinting codes and the fingerprinting capacity. Ehsan Amiri, Gábor Tardos |
| 2009 | How hard is it to approximate the best Nash equilibrium? Elad Hazan, Robert Krauthgamer |
| 2009 | Hypergraph regularity and quasi-randomness. Brendan Nagle, Annika Poerschke, Vojtech Rödl, Mathias Schacht |
| 2009 | Improved approximating algorithms for Directed Steiner Forest. Moran Feldman, Guy Kortsarz, Zeev Nutov |
| 2009 | Improved approximation algorithms for scheduling with fixed jobs. Florian Diedrich, Klaus Jansen |
| 2009 | Improved approximation bound for quadratic optimization problems with orthogonality constraints. Anthony Man-Cho So |
| 2009 | Improved bounds and new techniques for Davenport-Schinzel sequences and their generalizations. Gabriel Nivasch |
| 2009 | Improved equilibria via public service advertising. Maria-Florina Balcan, Avrim Blum, Yishay Mansour |
| 2009 | Improved smoothed analysis of the Bodo Manthey, Heiko Röglin |
| 2009 | Inserting a vertex into a planar graph. Markus Chimani, Carsten Gutwenger, Petra Mutzel, Christian Wolf |
| 2009 | Line transversals of convex polyhedra in Haim Kaplan, Natan Rubin, Micha Sharir |
| 2009 | Linear-time algorithms for geometric graphs with sublinearly many crossings. David Eppstein, Michael T. Goodrich, Darren Strash |
| 2009 | List-color-critical graphs on a fixed surface. Ken-ichi Kawarabayashi, Bojan Mohar |
| 2009 | Loopless generation of multiset permutations using a constant number of variables by prefix shifts. Aaron Williams |
| 2009 | Maximal biconnected subgraphs of random planar graphs. Konstantinos Panagiotou, Angelika Steger |
| 2009 | Maximizing submodular set functions subject to multiple linear constraints. Ariel Kulik, Hadas Shachnai, Tami Tamir |
| 2009 | Maximum independent set of rectangles. Parinya Chalermsook, Julia Chuzhoy |
| 2009 | Monotone minimal perfect hashing: searching a sorted table with Djamal Belazzougui, Paolo Boldi, Rasmus Pagh, Sebastiano Vigna |
| 2009 | Multi-dimensional online tracking. Ke Yi, Qin Zhang |
| 2009 | Natural algorithms. Bernard Chazelle |
| 2009 | On low dimensional local embeddings. Ittai Abraham, Yair Bartal, Ofer Neiman |
| 2009 | On risks of using cuckoo hashing with simple universal hash classes. Martin Dietzfelbinger, Ulf Schellbach |
| 2009 | On smoothed Amin Coja-Oghlan, Uriel Feige, Alan M. Frieze, Michael Krivelevich, Dan Vilenchik |
| 2009 | On stars and Steiner stars: II. Adrian Dumitrescu, Csaba D. Tóth, Guangwu Xu |
| 2009 | On the approximability of Dodgson and Young elections. Ioannis Caragiannis, Jason A. Covey, Michal Feldman, Christopher M. Homan, Christos Kaklamanis, Nikos Karanikolas, Ariel D. Procaccia, Jeffrey S. Rosenschein |
| 2009 | On the approximability of the maximum feasible subsystem problem with 0/1-coefficients. Khaled M. Elbassioni, Rajiv Raman, Saurabh Ray, René Sitters |
| 2009 | On the bit-complexity of Lempel-Ziv compression. Paolo Ferragina, Igor Nitto, Rossano Venturini |
| 2009 | On the complexity of Nash equilibria of action-graph games. Constantinos Daskalakis, Grant Schoenebeck, Gregory Valiant, Paul Valiant |
| 2009 | On the hitting times of quantum versus random walks. Frédéric Magniez, Ashwin Nayak, Peter C. Richter, Miklos Santha |
| 2009 | On the maximum quadratic assignment problem. Viswanath Nagarajan, Maxim Sviridenko |
| 2009 | On the power of two, three and four probes. Noga Alon, Uriel Feige |
| 2009 | On the relative strength of split, triangle and quadrilateral cuts. Amitabh Basu, Pierre Bonami, Gérard Cornuéjols, François Margot |
| 2009 | Online scheduling to minimize the maximum delay factor. Chandra Chekuri, Benjamin Moseley |
| 2009 | Online story scheduling in web advertising. Anirban Dasgupta, Arpita Ghosh, Hamid Nazerzadeh, Prabhakar Raghavan |
| 2009 | Optimal halfspace range reporting in three dimensions. Peyman Afshani, Timothy M. Chan |
| 2009 | Optimality of belief propagation for random assignment problem. J. Salez, D. Shah |
| 2009 | Overcoming the Alexandr Andoni, Piotr Indyk, Robert Krauthgamer |
| 2009 | Packing multiway cuts in capacitated graphs. Siddharth Barman, Shuchi Chawla |
| 2009 | Paging and list update under bijective analysis. Spyros Angelopoulos, Pascal Schweitzer |
| 2009 | Pairing heaps with Amr Elmasry |
| 2009 | Parameterized approximation scheme for the multiple knapsack problem. Klaus Jansen |
| 2009 | Partitioning graphs into balanced components. Robert Krauthgamer, Joseph Naor, Roy Schwartz |
| 2009 | Perfect matchings via uniform sampling in regular bipartite graphs. Ashish Goel, Michael Kapralov, Sanjeev Khanna |
| 2009 | Persistent homology for kernels, images, and cokernels. David Cohen-Steiner, Herbert Edelsbrunner, John Harer, Dmitriy Morozov |
| 2009 | Probability, algorithms and complexity. Volker Strassen |
| 2009 | Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2009, New York, NY, USA, January 4-6, 2009 Claire Mathieu |
| 2009 | Reasoning about online algorithms with weighted automata. Benjamin Aminof, Orna Kupferman, Robby Lampert |
| 2009 | Robust PCA and clustering in noisy mixtures. S. Charles Brubaker |
| 2009 | Sampling biased lattice configurations using exponential metrics. Sam Greenberg, Amanda Pascoe, Dana Randall |
| 2009 | Scalably scheduling processes with arbitrary speedup curves. Jeff Edmonds, Kirk Pruhs |
| 2009 | Secretary problems: weights and discounts. Moshe Babaioff, Michael Dinitz, Anupam Gupta, Nicole Immorlica, Kunal Talwar |
| 2009 | Self-overlapping curves revisited. David Eppstein, Elena Mumford |
| 2009 | Sequential cavity method for computing limits of the log-partition function for lattice models. David Gamarnik, Dmitriy Katz |
| 2009 | Shortest paths in directed planar graphs with negative lengths: a linear-space Philip N. Klein, Shay Mozes, Oren Weimann |
| 2009 | Size complexity of volume meshes vs. surface meshes. Benoît Hudson, Gary L. Miller, Todd Phillips, Don Sheehy |
| 2009 | Sorting and selection in posets. Constantinos Daskalakis, Richard M. Karp, Elchanan Mossel, Samantha J. Riesenfeld, Elad Verbin |
| 2009 | Sorting by placement and shift. Sergi Elizalde, Peter Winkler |
| 2009 | Speed scaling with an arbitrary power function. Nikhil Bansal, Ho-Leung Chan, Kirk Pruhs |
| 2009 | Stepwise randomized combinatorial auctions achieve revenue monotonicity. Baharak Rastegari, Anne Condon, Kevin Leyton-Brown |
| 2009 | Stream sampling for variance-optimal estimation of subset sums. Edith Cohen, Nick G. Duffield, Haim Kaplan, Carsten Lund, Mikkel Thorup |
| 2009 | String hashing for linear probing. Mikkel Thorup |
| 2009 | Succinct geometric indexes supporting point location queries. Prosenjit Bose, Eric Y. Chen, Meng He, Anil Maheshwari, Pat Morin |
| 2009 | Termination criteria for solving concurrent safety and reachability games. Krishnendu Chatterjee, Luca de Alfaro, Thomas A. Henzinger |
| 2009 | Testing halfspaces. Kevin Matulef, Ryan O'Donnell, Ronitt Rubinfeld, Rocco A. Servedio |
| 2009 | The Johnson-Lindenstrauss lemma almost characterizes Hilbert space, but not quite. William B. Johnson, Assaf Naor |
| 2009 | The complexity of simulating Brownian Motion. Ilia Binder, Mark Braverman |
| 2009 | The cover time of random geometric graphs. Colin Cooper, Alan M. Frieze |
| 2009 | The extended Lorenz Minder, Alistair Sinclair |
| 2009 | The geometry of binary search trees. Erik D. Demaine, Dion Harmon, John Iacono, Daniel Kane, Mihai Patrascu |
| 2009 | The ratio index for budgeted learning, with applications. Ashish Goel, Sanjeev Khanna, Brad Null |
| 2009 | The uniform hardcore lemma via approximate Bregman projections. Boaz Barak, Moritz Hardt, Satyen Kale |
| 2009 | The unreasonable effectiveness of martingales. Yuval Peres |
| 2009 | Three-coloring triangle-free planar graphs in linear time. Zdenek Dvorák, Ken-ichi Kawarabayashi, Robin Thomas |
| 2009 | Towards computing the Grothendieck constant. Prasad Raghavendra, David Steurer |
| 2009 | Transitive-closure spanners. Arnab Bhattacharyya, Elena Grigorescu, Kyomin Jung, Sofya Raskhodnikova, David P. Woodruff |
| 2009 | Weighted flow time does not admit O(1)-competitive algorithms. Nikhil Bansal, Ho-Leung Chan |