| 2007 | On the Hardness and Smoothed Complexity of Quasi-Concave Minimization. | Jonathan A. Kelner, Evdokia Nikolova |
| 2007 | Sparse Random Linear Codes are Locally Decodable and Testable. | Tali Kaufman, Madhu Sudan |
| 2007 | Balloon Popping With Applications to Ascending Auctions. | Nicole Immorlica, Anna R. Karlin, Mohammad Mahdian, Kunal Talwar |
| 2007 | Exponential Time/Space Speedups for Resolution and the PSPACE-completeness of Black-White Pebbling. | Philipp Hertel, Toniann Pitassi |
| 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 | Approximation Algorithms for Partial-Information Based Stochastic Control with Markovian Rewards. | Sudipto Guha, Kamesh Munagala |
| 2007 | Hardness of Reconstructing Multivariate Polynomials over Finite Fields. | Parikshit Gopalan, Subhash Khot, Rishi Saket |
| 2007 | Reconstruction for Models on Random Graphs. | Antoine Gerschenfeld, Andrea Montanari |
| 2007 | Integrality gaps of 2 - o(1) for Vertex Cover SDPs in the Lovsz-Schrijver Hierarchy. | Konstantinos Georgiou, Avner Magen, Toniann Pitassi, Iannis Tourlakis |
| 2007 | Minimizing Average Flow-time: Upper and Lower Bounds. | Naveen Garg, Amit Kumar |
| 2007 | Round Complexity of Authenticated Broadcast with a Dishonest Majority. | Juan A. Garay, Jonathan Katz, Chiu-Yuen Koo, Rafail Ostrovsky |
| 2007 | Lower Bounds on Streaming Algorithms for Approximating the Length of the Longest Increasing Subsequence. | Anna Gl, Parikshit Gopalan |
| 2007 | Approximate Hypergraph Partitioning and Applications. | Eldar Fischer, Arie Matsliah, Asaf Shapira |
| 2007 | Maximizing Non-Monotone Submodular Functions. | Uriel Feige, Vahab S. Mirrokni, Jan Vondrk |
| 2007 | Refuting Smoothed 3CNF Formulas. | Uriel Feige |
| 2007 | Almost Tight Bound for the Union of Fat Tetrahedra in Three Dimensions. | Esther Ezra, Micha Sharir |
| 2007 | On the Complexity of Nash Equilibria and Other Fixed Points (Extended Abstract). | Kousha Etessami, Mihalis Yannakakis |
| 2007 | Intrusion-Resilient Secret Sharing. | Stefan Dziembowski, Krzysztof Pietrzak |
| 2007 | Extractors and Rank Extractors for Polynomial Sources. | Zeev Dvir, Ariel Gabizon, Avi Wigderson |
| 2007 | Testing for Concise Representations. | Ilias Diakonikolas, Homin K. Lee, Kevin Matulef, Krzysztof Onak, Ronitt Rubinfeld, Rocco A. Servedio, Andrew Wan |
| 2007 | Computing Equilibria in Anonymous Games. | Constantinos Daskalakis, Christos H. Papadimitriou |
| 2007 | Parameterized Proof Complexity. | Stefan S. Dantchev, Barnaby Martin, Stefan Szeider |
| 2007 | Testing Expansion in Bounded-Degree Graphs. | Artur Czumaj, Christian Sohler |
| 2007 | Approximation Algorithms Using Hierarchies of Semidefinite Programming Relaxations. | Eden Chlamtac |
| 2007 | Quantum Algorithms for Hidden Nonlinear Structures. | Andrew M. Childs, Leonard J. Schulman, Umesh V. Vazirani |