| 2007 | Search via quantum walk. | Frdric Magniez, Ashwin Nayak, Jrmie Roland, Miklos Santha |
| 2007 | Distributed computing theory: algorithms, impossibility results, models, and proofs. | Nancy A. Lynch |
| 2007 | Lower bounds in communication complexity based on factorization norms. | Nati Linial, Adi Shraibman |
| 2007 | Survivable network design with degree or order constraints. | Lap Chi Lau, Joseph Naor, Mohammad R. Salavatipour, Mohit Singh |
| 2007 | On the convergence of Newton's method for monotone systems of polynomial equations. | Stefan Kiefer, Michael Luttenberger, Javier Esparza |
| 2007 | How to rank with few errors. | Claire Kenyon-Mathieu, Warren Schudy |
| 2007 | Computing crossing number in linear time. | Ken-ichi Kawarabayashi, Bruce A. Reed |
| 2007 | On achieving the "best of both worlds" in secure multiparty computation. | Jonathan Katz |
| 2007 | Playing games with approximation algorithms. | Sham M. Kakade, Adam Tauman Kalai, Katrina Ligett |
| 2007 | Eisenberg-Gale markets: algorithms and structural properties. | Kamal Jain, Vijay V. Vazirani |
| 2007 | Zero-knowledge from secure multiparty computation. | Yuval Ishai, Eyal Kushilevitz, Rafail Ostrovsky, Amit Sahai |
| 2007 | Uncertainty principles, extractors, and explicit embeddings of l2 into l1. | Piotr Indyk |
| 2007 | Negative weights make adversaries stronger. | Peter Hyer, Troy Lee, Robert Spalek |
| 2007 | Parallel repetition: simplifications and the no-signaling case. | Thomas Holenstein |
| 2007 | Interval completion with few edges. | Pinar Heggernes, Christophe Paul, Jan Arne Telle, Yngve Villanger |
| 2007 | Randomly coloring planar graphs with fewer colors than the maximum degree. | Thomas P. Hayes, Juan Carlos Vera, Eric Vigoda |
| 2007 | Tensor-based hardness of the shortest vector problem to within almost polynomial factors. | Ishay Haviv, Oded Regev |
| 2007 | The communication complexity of uncoupled nash equilibrium procedures. | Sergiu Hart, Yishay Mansour |
| 2007 | An (mn) Gomory-Hu tree construction algorithm for unweighted graphs. | Ramesh Hariharan, Telikepalli Kavitha, Debmalya Panigrahi, Anand Bhalgat |
| 2007 | Statistically-hiding commitment from any one-way function. | Iftach Haitner, Omer Reingold |
| 2007 | Toward a general theory of quantum games. | Gus Gutoski, John Watrous |
| 2007 | A 3-query PCP over integers. | Venkatesan Guruswami, Prasad Raghavendra |
| 2007 | Approximation algorithms for budgeted learning problems. | Sudipto Guha, Kamesh Munagala |
| 2007 | Verifying and decoding in constant depth. | Shafi Goldwasser, Dan Gutfreund, Alexander Healy, Tali Kaufman, Guy N. Rothblum |
| 2007 | Inapproximability of the Tutte polynomial. | Leslie Ann Goldberg, Mark Jerrum |