| 2007 | One sketch for all: fast algorithms for compressed sensing. | Anna C. Gilbert, Martin J. Strauss, Joel A. Tropp, Roman Vershynin |
| 2007 | Exponential separations for one-way quantum communication complexity, with applications to cryptography. | Dmitry Gavinsky, Julia Kempe, Iordanis Kerenidis, Ran Raz, Ronald de Wolf |
| 2007 | Faster integer multiplication. | Martin Frer |
| 2007 | Optimal suffix selection. | Gianni Franceschini, S. Muthukrishnan |
| 2007 | Reordering buffers for general metric spaces. | Matthias Englert, Harald Rcke, Matthias Westermann |
| 2007 | The price of privacy and the limits of LP decoding. | Cynthia Dwork, Frank McSherry, Kunal Talwar |
| 2007 | Iteratively constructing preconditioners via the conjugate gradient method. | John Dunagan, Nicholas J. A. Harvey |
| 2007 | Degree-constrained network flows. | Patrick Donovan, F. Bruce Shepherd, Adrian Vetta, Gordon T. Wilfong |
| 2007 | Limitations of VCG-based mechanisms. | Shahar Dobzinski, Noam Nisan |
| 2007 | Sampling-based dimension reduction for subspace approximation. | Amit Deshpande, Kasturi R. Varadarajan |
| 2007 | Rank complexity gap for Lovsz-Schrijver and Sherali-Adams proof systems. | Stefan S. Dantchev |
| 2007 | Polynomial flow-cut gaps and hardness of directed cut problems. | Julia Chuzhoy, Sanjeev Khanna |
| 2007 | Hardness of routing with congestion in directed graphs. | Julia Chuzhoy, Venkatesan Guruswami, Sanjeev Khanna, Kunal Talwar |
| 2007 | Voronoi diagrams in n·2 | Timothy M. Chan, Mihai Patrascu |
| 2007 | More algorithms for all-pairs shortest paths in weighted graphs. | Timothy M. Chan |
| 2007 | Holographic algorithms: from art to science. | Jin-yi Cai, Pinyan Lu |
| 2007 | Vertex cuts, random walks, and dimension reduction in series-parallel graphs. | Bo Brinkman, Adriana Karagiozova, James R. Lee |
| 2007 | Constructing non-computable Julia sets. | Mark Braverman, Michael Yampolsky |
| 2007 | First to market is not everything: an analysis of preferential attachment with fitness. | Christian Borgs, Jennifer T. Chayes, Constantinos Daskalakis, Sbastien Roch |
| 2007 | Fourier meets mbius: fast subset convolution. | Andreas Bjrklund, Thore Husfeldt, Petteri Kaski, Mikko Koivisto |
| 2007 | Lower bounds for randomized read/write stream algorithms. | Paul Beame, T. S. Jayram, Atri Rudra |
| 2007 | Simple deterministic approximation algorithms for counting matchings. | Mohsen Bayati, David Gamarnik, Dimitriy A. Katz, Chandra Nair, Prasad Tetali |
| 2007 | Combinatorial complexity in O-minimal geometry. | Saugata Basu |
| 2007 | Balanced max 2-sat might not be the hardest. | Per Austrin |
| 2007 | Tight bounds for asynchronous randomized consensus. | Hagit Attiya, Keren Censor |