| 2007 | Paths Beyond Local Search: A Tight Bound for Randomized Fixed-Point Computation. | Xi Chen, Shang-Hua Teng |
| 2007 | Derandomization of Sparse Cyclotomic Integer Zero Testing. | Qi Cheng |
| 2007 | Discrepancy and the Power of Bottom Fan-in in Depth-three Circuits. | Arkadev Chattopadhyay |
| 2007 | Local Global Tradeoffs in Metric Embeddings. | Moses Charikar, Konstantin Makarychev, Yury Makarychev |
| 2007 | On the Advantage over Random for Maximum Acyclic Subgraph. | Moses Charikar, Konstantin Makarychev, Yury Makarychev |
| 2007 | Covert Multi-Party Computation. | Nishanth Chandran, Vipul Goyal, Rafail Ostrovsky, Amit Sahai |
| 2007 | Cryptography from Sunspots: How to Use an Imperfect Reference String. | Ran Canetti, Rafael Pass, Abhi Shelat |
| 2007 | Smooth Histograms for Sliding Windows. | Vladimir Braverman, Rafail Ostrovsky |
| 2007 | Space-Efficient Identity Based Encryption Without Pairings. | Dan Boneh, Craig Gentry, Michael Hamburg |
| 2007 | A Brief Look at Pairings Based Cryptography. | Dan Boneh |
| 2007 | Pseudorandom Bits for Polynomials. | Andrej Bogdanov, Emanuele Viola |
| 2007 | Hardness Amplification for Errorless Heuristics. | Andrej Bogdanov, Muli Safra |
| 2007 | Strongly History-Independent Hashing with Applications. | Guy E. Blelloch, Daniel Golovin |
| 2007 | Inferring Local Homology from Sampled Stratified Spaces. | Paul Bendich, David Cohen-Steiner, Herbert Edelsbrunner, John Harer, Dmitriy Morozov |
| 2007 | Polylogarithmic Independence Can Fool DNF Formulas. | Louay Bazzi |
| 2007 | Lower Bounds on Signatures From Symmetric Primitives. | Boaz Barak, Mohammad Mahmoody-Ghidary |
| 2007 | Non-Preemptive Min-Sum Scheduling with Resource Augmentation. | Nikhil Bansal, Ho-Leung Chan, Rohit Khandekar, Kirk Pruhs, Clifford Stein, Baruch Schieber |
| 2007 | A Primal-Dual Randomized Algorithm for Weighted Paging. | Nikhil Bansal, Niv Buchbinder, Joseph Naor |
| 2007 | Towards Sharp Inapproximability For Any 2-CSP. | Per Austrin |
| 2007 | Buy-at-Bulk Network Design with Protection. | Spyridon Antonakopoulos, Chandra Chekuri, F. Bruce Shepherd, Lisa Zhang |
| 2007 | The Computational Hardness of Estimating Edit Distance [Extended Abstract]. | Alexandr Andoni, Robert Krauthgamer |
| 2007 | Inapproximability Results for Sparsest Cut, Optimal Linear Arrangement, and Precedence Constrained Scheduling. | Christoph Ambhl, Monaldo Mastrolilli, Ola Svensson |
| 2007 | Any AND-OR Formula of Size N can be Evaluated in time N | Andris Ambainis, Andrew M. Childs, Ben Reichardt, Robert Spalek, Shengyu Zhang |
| 2007 | Finding Disjoint Paths in Expanders Deterministically and Online. | Noga Alon, Michael R. Capalbo |
| 2007 | The Power of Quantum Systems on a Line. | Dorit Aharonov, Daniel Gottesman, Sandy Irani, Julia Kempe |