| 2007 | 48th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2007, Providence, RI, USA, October 20-23, 2007, Proceedings |
| 2007 | A Brief Look at Pairings Based Cryptography. Dan Boneh |
| 2007 | A Lower Bound for the Size of Syntactically Multilinear Arithmetic Circuits. Ran Raz, Amir Shpilka, Amir Yehudayoff |
| 2007 | A Primal-Dual Randomized Algorithm for Weighted Paging. Nikhil Bansal, Niv Buchbinder, Joseph Naor |
| 2007 | Adaptive Simulated Annealing: A Near-optimal Connection between Sampling and Counting. Daniel Stefankovic, Santosh S. Vempala, Eric Vigoda |
| 2007 | Almost Tight Bound for the Union of Fat Tetrahedra in Three Dimensions. Esther Ezra, Micha Sharir |
| 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 | Approximate Hypergraph Partitioning and Applications. Eldar Fischer, Arie Matsliah, Asaf Shapira |
| 2007 | Approximation Algorithms Using Hierarchies of Semidefinite Programming Relaxations. Eden Chlamtac |
| 2007 | Approximation Algorithms for Partial-Information Based Stochastic Control with Markovian Rewards. Sudipto Guha, Kamesh Munagala |
| 2007 | Balloon Popping With Applications to Ascending Auctions. Nicole Immorlica, Anna R. Karlin, Mohammad Mahdian, Kunal Talwar |
| 2007 | Beating Simplex for Fractional Packing and Covering Linear Programs. Christos Koufogiannakis, Neal E. Young |
| 2007 | Buy-at-Bulk Network Design with Protection. Spyridon Antonakopoulos, Chandra Chekuri, F. Bruce Shepherd, Lisa Zhang |
| 2007 | Can you beat treewidth? Dániel Marx |
| 2007 | Computing Equilibria in Anonymous Games. Constantinos Daskalakis, Christos H. Papadimitriou |
| 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 | 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 | Exponential Time/Space Speedups for Resolution and the PSPACE-completeness of Black-White Pebbling. Philipp Hertel, Toniann Pitassi |
| 2007 | Extractors and Rank Extractors for Polynomial Sources. Zeev Dvir, Ariel Gabizon, Avi Wigderson |
| 2007 | Finding Collisions in Interactive Protocols - A Tight Lower Bound on the Round Complexity of Statistically-Hiding Commitments. Iftach Haitner, Jonathan J. Hoch, Omer Reingold, Gil Segev |
| 2007 | Finding Disjoint Paths in Expanders Deterministically and Online. Noga Alon, Michael R. Capalbo |
| 2007 | Hardness Amplification for Errorless Heuristics. Andrej Bogdanov, Muli Safra |
| 2007 | Hardness of Reconstructing Multivariate Polynomials over Finite Fields. Parikshit Gopalan, Subhash Khot, Rishi Saket |
| 2007 | Inapproximability Results for Sparsest Cut, Optimal Linear Arrangement, and Precedence Constrained Scheduling. Christoph Ambühl, Monaldo Mastrolilli, Ola Svensson |
| 2007 | Inferring Local Homology from Sampled Stratified Spaces. Paul Bendich, David Cohen-Steiner, Herbert Edelsbrunner, John Harer, Dmitriy Morozov |
| 2007 | Integrality gaps of 2 - o(1) for Vertex Cover SDPs in the Lovész-Schrijver Hierarchy. Konstantinos Georgiou, Avner Magen, Toniann Pitassi, Iannis Tourlakis |
| 2007 | Intrusion-Resilient Secret Sharing. Stefan Dziembowski, Krzysztof Pietrzak |
| 2007 | Linear Equations Modulo 2 and the L1 Diameter of Convex Bodies. Subhash Khot, Assaf Naor |
| 2007 | Local Global Tradeoffs in Metric Embeddings. Moses Charikar, Konstantin Makarychev, Yury Makarychev |
| 2007 | Lower Bounds on Signatures From Symmetric Primitives. Boaz Barak, Mohammad Mahmoody-Ghidary |
| 2007 | Lower Bounds on Streaming Algorithms for Approximating the Length of the Longest Increasing Subsequence. Anna Gál, Parikshit Gopalan |
| 2007 | Maximizing Non-Monotone Submodular Functions. Uriel Feige, Vahab S. Mirrokni, Jan Vondrák |
| 2007 | Mechanism Design via Differential Privacy. Frank McSherry, Kunal Talwar |
| 2007 | Minimizing Average Flow-time: Upper and Lower Bounds. Naveen Garg, Amit Kumar |
| 2007 | Mixing Time Power Laws at Criticality. Yun Long, Asaf Nachmias, Yuval Peres |
| 2007 | Near Optimal Bounds for Collision in Pollard Rho for Discrete Log. Jeong Han Kim, Ravi Montenegro, Prasad Tetali |
| 2007 | Non-Linear Index Coding Outperforming the Linear Optimum. Eyal Lubetzky, Uri Stav |
| 2007 | Non-Preemptive Min-Sum Scheduling with Resource Augmentation. Nikhil Bansal, Ho-Leung Chan, Rohit Khandekar, Kirk Pruhs, Clifford Stein, Baruch Schieber |
| 2007 | On the Advantage over Random for Maximum Acyclic Subgraph. Moses Charikar, Konstantin Makarychev, Yury Makarychev |
| 2007 | On the Complexity of Nash Equilibria and Other Fixed Points (Extended Abstract). Kousha Etessami, Mihalis Yannakakis |
| 2007 | On the Hardness and Smoothed Complexity of Quasi-Concave Minimization. Jonathan A. Kelner, Evdokia Nikolova |
| 2007 | On the Optimality of Planar and Geometric Approximation Schemes. Dániel Marx |
| 2007 | One-Way Multi-Party Communication Lower Bound for Pointer Jumping with Applications. Emanuele Viola, Avi Wigderson |
| 2007 | Parameterized Proof Complexity. Stefan S. Dantchev, Barnaby Martin, Stefan Szeider |
| 2007 | Paths Beyond Local Search: A Tight Bound for Randomized Fixed-Point Computation. Xi Chen, Shang-Hua Teng |
| 2007 | Planning for Fast Connectivity Updates. Mihai Patrascu, Mikkel Thorup |
| 2007 | Polylogarithmic Independence Can Fool DNF Formulas. Louay Bazzi |
| 2007 | Pseudorandom Bits for Polynomials. Andrej Bogdanov, Emanuele Viola |
| 2007 | Quantum Algorithms for Hidden Nonlinear Structures. Andrew M. Childs, Leonard J. Schulman, Umesh V. Vazirani |
| 2007 | Reconstruction for Models on Random Graphs. Antoine Gerschenfeld, Andrea Montanari |
| 2007 | Refuting Smoothed 3CNF Formulas. Uriel Feige |
| 2007 | Round Complexity of Authenticated Broadcast with a Dishonest Majority. Juan A. Garay, Jonathan Katz, Chiu-Yuen Koo, Rafail Ostrovsky |
| 2007 | Simulating Quantum Correlations with Finite Communication. Oded Regev, Ben Toner |
| 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 | Sparse Random Linear Codes are Locally Decodable and Testable. Tali Kaufman, Madhu Sudan |
| 2007 | Spectral Graph Theory and its Applications. Daniel A. Spielman |
| 2007 | Strong Lower Bounds for Approximating Distribution Support Size and the Distinct Elements Problem. Sofya Raskhodnikova, Dana Ron, Amir Shpilka, Adam D. Smith |
| 2007 | Strongly History-Independent Hashing with Applications. Guy E. Blelloch, Daniel Golovin |
| 2007 | Structure and Randomness in Combinatorics. Terence Tao |
| 2007 | Testing Expansion in Bounded-Degree Graphs. Artur Czumaj, Christian Sohler |
| 2007 | Testing for Concise Representations. Ilias Diakonikolas, Homin K. Lee, Kevin Matulef, Krzysztof Onak, Ronitt Rubinfeld, Rocco A. Servedio, Andrew Wan |
| 2007 | The Computational Hardness of Estimating Edit Distance [Extended Abstract]. Alexandr Andoni, Robert Krauthgamer |
| 2007 | The Power of Quantum Systems on a Line. Dorit Aharonov, Daniel Gottesman, Sandy Irani, Julia Kempe |
| 2007 | Towards Sharp Inapproximability For Any 2-CSP. Per Austrin |