| 2005 | A new strategy for querying priced information. Ferdinando Cicalese, Eduardo Sany Laber |
| 2005 | Aggregating inconsistent information: ranking and clustering. Nir Ailon, Moses Charikar, Alantha Newman |
| 2005 | An O(log n log log n) space algorithm for undirected st-connectivity. Vladimir Trifonov |
| 2005 | An optimal multi-writer snapshot algorithm. Prasad Jayanti |
| 2005 | Approximately counting integral flows and cell-bounded contingency tables. Mary Cryan, Martin E. Dyer, Dana Randall |
| 2005 | Approximation algorithms for combinatorial auctions with complement-free bidders. Shahar Dobzinski, Noam Nisan, Michael Schapira |
| 2005 | Approximation algorithms for network design with metric costs. Joseph Cheriyan, Adrian Vetta |
| 2005 | Approximation techniques for utilitarian mechanism design. Patrick Briest, Piotr Krysta, Berthold Vöcking |
| 2005 | Balanced boolean functions that can be evaluated so that every input bit is unlikely to be read. Itai Benjamini, Oded Schramm, David Bruce Wilson |
| 2005 | Balanced metric labeling. Joseph Naor, Roy Schwartz |
| 2005 | Beyond NP: the work and legacy of Larry Stockmeyer. Lance Fortnow |
| 2005 | Bounded-depth circuits: separating wires from gates. Michal Koucký, Pavel Pudlák, Denis Thérien |
| 2005 | Collusion-free protocols. Matt Lepinski, Silvio Micali, Abhi Shelat |
| 2005 | Computing correlated equilibria in multi-player games. Christos H. Papadimitriou |
| 2005 | Computing the first Betti number and the connected components of semi-algebraic sets. Saugata Basu, Richard Pollack, Marie-Françoise Roy |
| 2005 | Concurrent general composition of secure protocols in the timing model. Yael Tauman Kalai, Yehuda Lindell, Manoj Prabhakaran |
| 2005 | Convex programming for scheduling unrelated parallel machines. Yossi Azar, Amir Epstein |
| 2005 | Cooperative asynchronous update of shared memory. Bogdan S. Chlebus, Dariusz R. Kowalski |
| 2005 | Coresets in dynamic geometric data streams. Gereon Frahling, Christian Sohler |
| 2005 | Correcting errors without leaking partial information. Yevgeniy Dodis, Adam D. Smith |
| 2005 | Covert two-party computation. Luis von Ahn, Nicholas J. Hopper, John Langford |
| 2005 | Derandomization of auctions. Gagan Aggarwal, Amos Fiat, Andrew V. Goldberg, Jason D. Hartline, Nicole Immorlica, Madhu Sudan |
| 2005 | Edge partition of planar sraphs into two outerplanar graphs. Daniel Gonçalves |
| 2005 | Efficient testing of groups. Katalin Friedl, Gábor Ivanyos, Miklos Santha |
| 2005 | Euclidean distortion and the sparsest cut. Sanjeev Arora, James R. Lee, Assaf Naor |
| 2005 | Every 2-CSP allows nontrivial approximation. Johan Håstad |
| 2005 | Every monotone graph property is testable. Noga Alon, Asaf Shapira |
| 2005 | Extractors with weak random seeds. Ran Raz |
| 2005 | Fast quantum algorithms for computing the unit group and class group of a number field. Sean Hallgren |
| 2005 | Fast quantum byzantine agreement. Michael Ben-Or, Avinatan Hassidim |
| 2005 | From a static impossibility to an adaptive lower bound: the complexity of early deciding set agreement. Eli Gafni, Rachid Guerraoui, Bastian Pochon |
| 2005 | Hardness of the undirected congestion minimization problem. Matthew Andrews, Lisa Zhang |
| 2005 | Hardness of the undirected edge-disjoint paths problem. Matthew Andrews, Lisa Zhang |
| 2005 | Hierarchies for semantic classes. Lance Fortnow, Rahul Santhanam, Luca Trevisan |
| 2005 | How to spread adversarial nodes?: rotate! Christian Scheideler |
| 2005 | Improved approximation algorithms for minimum-weight vertex separators. Uriel Feige, Mohammad Taghi Hajiaghayi, James R. Lee |
| 2005 | Key agreement from weak bit agreement. Thomas Holenstein |
| 2005 | Learning nonsingular phylogenies and hidden Markov models. Elchanan Mossel, Sébastien Roch |
| 2005 | Learning with attribute costs. Haim Kaplan, Eyal Kushilevitz, Yishay Mansour |
| 2005 | Limits to list decoding Reed-Solomon codes. Venkatesan Guruswami, Atri Rudra |
| 2005 | Locally decodable codes with 2 queries and polynomial identity testing for depth 3 circuits. Zeev Dvir, Amir Shpilka |
| 2005 | Low distortion embeddings for edit distance. Rafail Ostrovsky, Yuval Rabani |
| 2005 | Low-distortion embeddings of general metrics into the line. Mihai Badoiu, Julia Chuzhoy, Piotr Indyk, Anastasios Sidiropoulos |
| 2005 | Lower bounds for k-DNF resolution on random 3-CNFs. Michael Alekhnovich |
| 2005 | Lower-stretch spanning trees. Michael Elkin, Yuval Emek, Daniel A. Spielman, Shang-Hua Teng |
| 2005 | Market equilibrium via the excess demand function. Bruno Codenotti, Benton McCune, Kasturi R. Varadarajan |
| 2005 | Multicommodity flow, well-linked terminals, and routing problems. Chandra Chekuri, Sanjeev Khanna, F. Bruce Shepherd |
| 2005 | New and improved constructions of non-malleable cryptographic protocols. Rafael Pass, Alon Rosen |
| 2005 | O(sqrt(log n)) approximation algorithms for min UnCut, min 2CNF deletion, and directed cut problems. Amit Agarwal, Moses Charikar, Konstantin Makarychev, Yury Makarychev |
| 2005 | Oblivious routing in directed graphs with random demands. Mohammad Taghi Hajiaghayi, Jeong Han Kim, Tom Leighton, Harald Räcke |
| 2005 | On algorithms for discrete and approximate brouwer fixed points. Xi Chen, Xiaotie Deng |
| 2005 | On dynamic range reporting in one dimension. Christian Worm Mortensen, Rasmus Pagh, Mihai Patrascu |
| 2005 | On lattices, learning with errors, random linear codes, and cryptography. Oded Regev |
| 2005 | On non-uniform multicommodity buy-at-bulk network design. Moses Charikar, Adriana Karagiozova |
| 2005 | On obfuscating point functions. Hoeteck Wee |
| 2005 | On random pm 1 matrices: singularity and determinant. Terence Tao, Van H. Vu |
| 2005 | On strip packing With rotations. Klaus Jansen, Rob van Stee |
| 2005 | On the average case performance of some greedy approximation algorithms for the uncapacitated facility location problem. Abraham Flaxman, Alan M. Frieze, Juan Carlos Vera |
| 2005 | On the bias of traceroute sampling: or, power-law degree distributions in regular graphs. Dimitris Achlioptas, Aaron Clauset, David Kempe, Cristopher Moore |
| 2005 | On uniform amplification of hardness in NP. Luca Trevisan |
| 2005 | Optimal approximations of the frequency moments of data streams. Piotr Indyk, David P. Woodruff |
| 2005 | Polynomial time algorithm for computing the top Betti numbers of semi-algebraic sets defined by quadratic inequalities. Saugata Basu |
| 2005 | Polynomial time quantum algorithm for the computation of the unit group of a number field. Arthur Schmidt, Ulrich Vollmer |
| 2005 | Proceedings of the 37th Annual ACM Symposium on Theory of Computing, Baltimore, MD, USA, May 22-24, 2005 Harold N. Gabow, Ronald Fagin |
| 2005 | Pseudorandom generators for low degree polynomials. Andrej Bogdanov |
| 2005 | Quadratic forms on graphs. Noga Alon, Konstantin Makarychev, Yury Makarychev, Assaf Naor |
| 2005 | Representing hard lattices with O(n log n) bits. Miklós Ajtai |
| 2005 | Saving an epsilon: a 2-approximation for the k-MST problem in graphs. Naveen Garg |
| 2005 | Simple PCPs with poly-log rate and query complexity. Eli Ben-Sasson, Madhu Sudan |
| 2005 | Simulating independence: new constructions of condensers, ramsey graphs, dispersers, and extractors. Boaz Barak, Guy Kindler, Ronen Shaltiel, Benny Sudakov, Avi Wigderson |
| 2005 | Spectral norm of random matrices. Van H. Vu |
| 2005 | Tensor decomposition and approximation schemes for constraint satisfaction problems. Wenceslas Fernandez de la Vega, Marek Karpinski, Ravi Kannan, Santosh S. Vempala |
| 2005 | Tensor norms and the classical communication complexity of nonlocal quantum measurement. Yaoyun Shi |
| 2005 | Testing monotone high-dimensional distributions. Ronitt Rubinfeld, Rocco A. Servedio |
| 2005 | Testing versus estimation of graph properties. Eldar Fischer, Ilan Newman |
| 2005 | The Price of Routing Unsplittable Flow. Baruch Awerbuch, Yossi Azar, Amir Epstein |
| 2005 | The complexity of agreement. Scott Aaronson |
| 2005 | The mixing time of the Thorp shuffle. Ben Morris |
| 2005 | The price of anarchy of finite congestion games. George Christodoulou, Elias Koutsoupias |
| 2005 | The round complexity of two-party random selection. Saurabh Sanghvi, Salil P. Vadhan |
| 2005 | Towards asymptotic optimality in probabilistic packet marking. Micah Adler, Jeff Edmonds, Jirí Matousek |
| 2005 | Towards strong nonapproximability results in the Lovasz-Schrijver hierarchy. Michael Alekhnovich, Sanjeev Arora, Iannis Tourlakis |
| 2005 | Tree-walking automata do not recognize all regular languages. Mikolaj Bojanczyk, Thomas Colcombet |
| 2005 | Undirected ST-connectivity in log-space. Omer Reingold |
| 2005 | Universal approximations for TSP, Steiner tree, and set cover. Lujun Jia, Guolong Lin, Guevara Noubir, Rajmohan Rajaraman, Ravi Sundaram |
| 2005 | Worst-case update times for fully-dynamic all-pairs shortest paths. Mikkel Thorup |