| 2003 | On the Impossibility of Dimension Reduction in l | Bo Brinkman, Moses Charikar |
| 2003 | On Worst-Case to Average-Case Reductions for NP Problems. | Andrej Bogdanov, Luca Trevisan |
| 2003 | Approximation Algorithms for Orienteering and Discounted-Reward TSP. | Avrim Blum, Shuchi Chawla, David R. Karger, Terran Lane, Adam Meyerson, Maria Minkoff |
| 2003 | Machine Learning: My Favorite Results, Directions, and Open Problems. | Avrim Blum |
| 2003 | Instability of FIFO at Arbitrarily Low Rates in the Adversarial Queueing Model. | Rajat Bhattacharjee, Ashish Goel |
| 2003 | Symmetric Polynomials over Z | Nayantara Bhatnagar, Parikshit Gopalan, Richard J. Lipton |
| 2003 | The Cost of Cache-Oblivious Searching. | Michael A. Bender, Gerth Stlting Brodal, Rolf Fagerberg, Dongdong Ge, Simai He, Haodong Hu, John Iacono, Alejandro Lpez-Ortiz |
| 2003 | Separating the Power of Monotone Span Programs over Different Fields. | Amos Beimel, Enav Weinreb |
| 2003 | Average Case and Smoothed Competitive Analysis of the Multi-Level Feedback Algorithm. | Luca Becchetti, Stefano Leonardi, Alberto Marchetti-Spaccamela, Guido Schfer, Tjark Vredeveld |
| 2003 | Lower Bounds for Non-Black-Box Zero Knowledge. | Boaz Barak, Yehuda Lindell, Salil P. Vadhan |
| 2003 | Algorithms and Complexity Results for #SAT and Bayesian Inference. | Fahiem Bacchus, Shannon Dalmao, Toniann Pitassi |
| 2003 | Locally Testable Cyclic Codes. | Lszl Babai, Amir Shpilka, Daniel Stefankovic |
| 2003 | I/O-Efficient Strong Connectivity and Depth-First Search for Directed Planar Graphs. | Lars Arge, Norbert Zeh |
| 2003 | Stability and Efficiency of a Random Local Load Balancing Protocol. | Aris Anagnostopoulos, Adam Kirsch, Eli Upfal |
| 2003 | Polynomial Degree vs. Quantum Query Complexity. | Andris Ambainis |
| 2003 | Linear Upper Bounds for Random Walk on Small Density Random 3-CNF. | Michael Alekhnovich, Eli Ben-Sasson |
| 2003 | More on Average Case vs Approximation Complexity. | Michael Alekhnovich |
| 2003 | Proving Hard-Core Predicates Using List Decoding. | Adi Akavia, Shafi Goldwasser, Shmuel Safra |
| 2003 | A Lattice Problem in Quantum NP. | Dorit Aharonov, Oded Regev |
| 2003 | Switch Scheduling via Randomized Edge Coloring. | Gagan Aggarwal, Rajeev Motwani, Devavrat Shah, An Zhu |
| 2003 | On the Maximum Satisfiability of Random Formulas. | Dimitris Achlioptas, Assaf Naor, Yuval Peres |
| 2003 | Quantum Search of Spatial Regions. | Scott Aaronson, Andris Ambainis |
| 2002 | imits on the Power of Quantum Statistical Zero-Knowledge. | John Watrous |
| 2002 | On-Line Confidence Machines Are Well-Calibrated. | Vladimir Vovk |
| 2002 | Nash Equilibria in Competitive Societies, with Applications to Facility Location, Traffic Routing and Auctions. | Adrian Vetta |