| 2002 | 3-MANIFOLD KNOT GENUS is NP-complete. Ian Agol, Joel Hass, William P. Thurston |
| 2002 | Algebras of Minimal Rank over Perfect Fields. Markus Bläser |
| 2002 | Algorithmic Derandomization via Complexity Theory. D. Sivakumar |
| 2002 | Arthur and Merlin in a Quantum World. John Watrous |
| 2002 | Better Lower Bounds for Locally Decodable Codes. Amit Deshpande, Rahul Jain, Telikepalli Kavitha, Jaikumar Radhakrishnan, Satyanarayana V. Lokam |
| 2002 | Decoding Concatenated Codes using Soft Information. Venkatesan Guruswami, Madhu Sudan |
| 2002 | Expanders from Symmetric Codes. Roy Meshulam, Avi Wigderson |
| 2002 | Extracting Quantum Entanglement. Andris Ambainis, Adam D. Smith, Ke Yang |
| 2002 | Functions that have Read-Twice Constant Width Branching Programs are not Necessarily Testable. Eldar Fischer, Ilan Newman |
| 2002 | Hard Examples for Bounded Depth Frege. Eli Ben-Sasson |
| 2002 | Hardness Amplification within NP. Ryan O'Donnell |
| 2002 | Improved Cryptographic Hash Functions with Worst-Case/Average-Case Connection. Daniele Micciancio |
| 2002 | Information Theory Methods in Communication Complexity. Ziv Bar-Yossef, T. S. Jayram, Ravi Kumar, D. Sivakumar |
| 2002 | Learnability beyond AC0. Jeffrey C. Jackson, Adam R. Klivans, Rocco A. Servedio |
| 2002 | Lower Bounds for Linear Locally Decodable Codes and Private Information Retrieval. Oded Goldreich, Howard J. Karloff, Leonard J. Schulman, Luca Trevisan |
| 2002 | On Communication over an Entanglement-Assisted Quantum Channel. Ashwin Nayak, Julia Salzman |
| 2002 | On the Complexity of Integer Multiplication in Branching Programs with Multiple Tests and in Read-Once Branching Programs with Limited Nondeterminism. Philipp Woelfel |
| 2002 | On the Power of Unique 2-Prover 1-Round Games. Subhash Khot |
| 2002 | Proceedings of the 17th Annual IEEE Conference on Computational Complexity, Montréal, Québec, Canada, May 21-24, 2002 |
| 2002 | Pseudo-Random Generators and Structure of Complete Degrees. Manindra Agrawal |
| 2002 | Pseudo-Random Generators for All Hardnesses. Christopher Umans |
| 2002 | Pseudorandomness and Average-Case Complexity via Uniform Reductions. Luca Trevisan, Salil P. Vadhan |
| 2002 | Randomness Conductors and Constant-Degree Lossless Expanders. Michael R. Capalbo, Omer Reingold, Salil P. Vadhan, Avi Wigderson |
| 2002 | Rapid Mixing. Peter Winkler |
| 2002 | Relations between Average Case Complexity and Approximation Complexity. Uriel Feige |
| 2002 | Resolution Lower Bounds for Perfect Matching Principles. Alexander A. Razborov |
| 2002 | Resolution Lower Bounds for the Weak Pigeonhole Principle. Ran Raz |
| 2002 | Resolution Width-Size Trade-offs for the Pigeon-Hole Principle. Stefan S. Dantchev |
| 2002 | Sampling Short Lattice Vectors and the Closest Lattice Vector Problem. Miklós Ajtai, Ravi Kumar, D. Sivakumar |
| 2002 | Streaming Computation of Combinatorial Objects. Ziv Bar-Yossef, Luca Trevisan, Omer Reingold, Ronen Shaltiel |
| 2002 | The Complexity of Approximating the Entropy. Tugkan Batu, Sanjoy Dasgupta, Ravi Kumar, Ronitt Rubinfeld |
| 2002 | The Correlation Between Parity and Quadratic Polynomials Mod 3. Frederic Green |
| 2002 | The History of Complexity. Lance Fortnow |
| 2002 | The Inapproximability of Lattice and Coding Problems with Preprocessing. Uriel Feige, Daniele Micciancio |
| 2002 | Time-Space Tradeoffs, Multiparty Communication Complexity, and Nearest-Neighbor Problems. Paul Beame, Erik Vee |
| 2002 | Universal Arguments and their Applications. Boaz Barak, Oded Goldreich |
| 2002 | Vertex Cover on 4-Regular Hyper-graphs Is Hard to Approximate within 2 - ε. Jonas Holmerin |