| 2007 | A 3-query PCP over integers. Venkatesan Guruswami, Prasad Raghavendra |
| 2007 | A combinatorial, primal-dual approach to semidefinite programs. Sanjeev Arora, Satyen Kale |
| 2007 | All-pairs bottleneck paths for general graphs in truly sub-cubic time. Virginia Vassilevska, Ryan Williams, Raphael Yuster |
| 2007 | An approximation algorithm for max-min fair allocation of indivisible goods. Arash Asadpour, Amin Saberi |
| 2007 | An efficient parallel repetition theorem for Arthur-Merlin games. Rafael Pass, Muthuramakrishnan Venkitasubramaniam |
| 2007 | An Õ(mn) Gomory-Hu tree construction algorithm for unweighted graphs. Ramesh Hariharan, Telikepalli Kavitha, Debmalya Panigrahi, Anand Bhalgat |
| 2007 | Approximating minimum bounded degree spanning trees to within one of optimal. Mohit Singh, Lap Chi Lau |
| 2007 | Approximation algorithms for budgeted learning problems. Sudipto Guha, Kamesh Munagala |
| 2007 | Balanced allocations: the weighted case. Kunal Talwar, Udi Wieder |
| 2007 | Balanced max 2-sat might not be the hardest. Per Austrin |
| 2007 | Circuit lower bounds for Merlin-Arthur classes. Rahul Santhanam |
| 2007 | Combinatorial complexity in O-minimal geometry. Saugata Basu |
| 2007 | Computing crossing number in linear time. Ken-ichi Kawarabayashi, Bruce A. Reed |
| 2007 | Constructing non-computable Julia sets. Mark Braverman, Michael Yampolsky |
| 2007 | Degree-constrained network flows. Patrick Donovan, F. Bruce Shepherd, Adrian Vetta, Gordon T. Wilfong |
| 2007 | Distributed computing theory: algorithms, impossibility results, models, and proofs. Nancy A. Lynch |
| 2007 | Eisenberg-Gale markets: algorithms and structural properties. Kamal Jain, Vijay V. Vazirani |
| 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 Fürer |
| 2007 | First to market is not everything: an analysis of preferential attachment with fitness. Christian Borgs, Jennifer T. Chayes, Constantinos Daskalakis, Sébastien Roch |
| 2007 | Fourier meets möbius: fast subset convolution. Andreas Björklund, Thore Husfeldt, Petteri Kaski, Mikko Koivisto |
| 2007 | Hardness of routing with congestion in directed graphs. Julia Chuzhoy, Venkatesan Guruswami, Sanjeev Khanna, Kunal Talwar |
| 2007 | Holographic algorithms: from art to science. Jin-Yi Cai, Pinyan Lu |
| 2007 | How to rank with few errors. Claire Kenyon-Mathieu, Warren Schudy |
| 2007 | Improved approximation for directed cut problems. Amit Agarwal, Noga Alon, Moses Charikar |
| 2007 | Inapproximability of the Tutte polynomial. Leslie Ann Goldberg, Mark Jerrum |
| 2007 | Interpolation of depth-3 arithmetic circuits with two multiplication gates. Amir Shpilka |
| 2007 | Interval completion with few edges. Pinar Heggernes, Christophe Paul, Jan Arne Telle, Yngve Villanger |
| 2007 | Iteratively constructing preconditioners via the conjugate gradient method. John Dunagan, Nicholas J. A. Harvey |
| 2007 | Lattices that admit logarithmic worst-case to average-case connection factors. Chris Peikert, Alon Rosen |
| 2007 | Limitations of VCG-based mechanisms. Shahar Dobzinski, Noam Nisan |
| 2007 | Linear probing with constant independence. Anna Pagh, Rasmus Pagh, Milan Ruzic |
| 2007 | Local embeddings of metric spaces. Ittai Abraham, Yair Bartal, Ofer Neiman |
| 2007 | Low-degree tests at large distances. Alex Samorodnitsky |
| 2007 | Low-end uniform hardness vs. randomness tradeoffs for AM. Ronen Shaltiel, Christopher Umans |
| 2007 | Lower bounds for 2-dimensional range counting. Mihai Patrascu |
| 2007 | Lower bounds for randomized read/write stream algorithms. Paul Beame, T. S. Jayram, Atri Rudra |
| 2007 | Lower bounds in communication complexity based on factorization norms. Nati Linial, Adi Shraibman |
| 2007 | More algorithms for all-pairs shortest paths in weighted graphs. Timothy M. Chan |
| 2007 | Negative weights make adversaries stronger. Peter Høyer, Troy Lee, Robert Spalek |
| 2007 | On achieving the "best of both worlds" in secure multiparty computation. Jonathan Katz |
| 2007 | On the convergence of Newton's method for monotone systems of polynomial equations. Stefan Kiefer, Michael Luttenberger, Javier Esparza |
| 2007 | On the impossibility of a quantum sieve algorithm for graph isomorphism. Cristopher Moore, Alexander Russell, Piotr Sniady |
| 2007 | On the submodularity of influence in social networks. Elchanan Mossel, Sébastien Roch |
| 2007 | One sketch for all: fast algorithms for compressed sensing. Anna C. Gilbert, Martin J. Strauss, Joel A. Tropp, Roman Vershynin |
| 2007 | Optimal suffix selection. Gianni Franceschini, S. Muthukrishnan |
| 2007 | Parallel repetition: simplifications and the no-signaling case. Thomas Holenstein |
| 2007 | Playing games with approximation algorithms. Sham M. Kakade, Adam Tauman Kalai, Katrina Ligett |
| 2007 | Polynomial flow-cut gaps and hardness of directed cut problems. Julia Chuzhoy, Sanjeev Khanna |
| 2007 | Proceedings of the 39th Annual ACM Symposium on Theory of Computing, San Diego, California, USA, June 11-13, 2007 David S. Johnson, Uriel Feige |
| 2007 | Property testing in hypergraphs and the removal lemma. Vojtech Rödl, Mathias Schacht |
| 2007 | Proportional response dynamics leads to market equilibrium. Fang Wu, Li Zhang |
| 2007 | Randomly coloring planar graphs with fewer colors than the maximum degree. Thomas P. Hayes, Juan Carlos Vera, Eric Vigoda |
| 2007 | Rank complexity gap for Lovász-Schrijver and Sherali-Adams proof systems. Stefan S. Dantchev |
| 2007 | Reordering buffers for general metric spaces. Matthias Englert, Harald Räcke, Matthias Westermann |
| 2007 | Sampling-based dimension reduction for subspace approximation. Amit Deshpande, Kasturi R. Varadarajan |
| 2007 | Search via quantum walk. Frédéric Magniez, Ashwin Nayak, Jérémie Roland, Miklos Santha |
| 2007 | Separating AC Alexander A. Sherstov |
| 2007 | Simple deterministic approximation algorithms for counting matchings. Mohsen Bayati, David Gamarnik, Dimitriy A. Katz, Chandra Nair, Prasad Tetali |
| 2007 | Smooth sensitivity and sampling in private data analysis. Kobbi Nissim, Sofya Raskhodnikova, Adam D. Smith |
| 2007 | Some new results on node-capacitated packing of A-paths. Gyula Pap |
| 2007 | Stability of the max-weight routing and scheduling protocol in dynamic networks and at critical loads. Matthew Andrews, Kyomin Jung, Alexander L. Stolyar |
| 2007 | Statistically-hiding commitment from any one-way function. Iftach Haitner, Omer Reingold |
| 2007 | Survivable network design with degree or order constraints. Lap Chi Lau, Joseph Naor, Mohammad R. Salavatipour, Mohit Singh |
| 2007 | Tensor-based hardness of the shortest vector problem to within almost polynomial factors. Ishay Haviv, Oded Regev |
| 2007 | Terminal backup, 3D matching, and covering cubic graphs. Elliot Anshelevich, Adriana Karagiozova |
| 2007 | Testing k-wise and almost k-wise independence. Noga Alon, Alexandr Andoni, Tali Kaufman, Kevin Matulef, Ronitt Rubinfeld, Ning Xie |
| 2007 | The communication complexity of uncoupled nash equilibrium procedures. Sergiu Hart, Yishay Mansour |
| 2007 | The condition number of a randomly perturbed matrix. Van H. Vu, Terence Tao |
| 2007 | The price of privacy and the limits of LP decoding. Cynthia Dwork, Frank McSherry, Kunal Talwar |
| 2007 | Tight bounds for asynchronous randomized consensus. Hagit Attiya, Keren Censor |
| 2007 | Tight integrality gaps for Lovasz-Schrijver LP relaxations of vertex cover and max cut. Grant Schoenebeck, Luca Trevisan, Madhur Tulsiani |
| 2007 | Toward a general theory of quantum games. Gus Gutoski, John Watrous |
| 2007 | Towards 3-query locally decodable codes of subexponential length. Sergey Yekhanin |
| 2007 | Uncertainty principles, extractors, and explicit embeddings of l2 into l1. Piotr Indyk |
| 2007 | Verifying and decoding in constant depth. Shafi Goldwasser, Dan Gutfreund, Alexander Healy, Tali Kaufman, Guy N. Rothblum |
| 2007 | Vertex cuts, random walks, and dimension reduction in series-parallel graphs. Bo Brinkman, Adriana Karagiozova, James R. Lee |
| 2007 | Voronoi diagrams in n·2 Timothy M. Chan, Mihai Patrascu |
| 2007 | Zero-knowledge from secure multiparty computation. Yuval Ishai, Eyal Kushilevitz, Rafail Ostrovsky, Amit Sahai |