| 2002 | Low-Dimensional Linear Programming with Violations. | Timothy M. Chan |
| 2002 | Packing 2-Dimensional Bins in Harmony. | Alberto Caprara |
| 2002 | Lower Bounds on the Bounded Coefficient Complexity of Bilinear Maps. | Peter Brgisser, Martin Lotz |
| 2002 | Bounded-Depth Frege Lower Bounds for Weaker Pigeonhole Principles. | Josh Buresh-Oppenheim, Paul Beame, Toniann Pitassi, Ran Raz, Ashish Sabharwal |
| 2002 | A Dichotomy Theorem for Constraints on a Three-Element Set. | Andrei A. Bulatov |
| 2002 | PAC = PAExact and Other Equivalent Models in Learning. | Nader H. Bshouty, Dmitry Gavinsky |
| 2002 | Dynamic Planar Convex Hull. | Gerth Stlting Brodal, Riko Jacob |
| 2002 | A Lower Bound for Testing 3-Colorability in Bounded-Degree Graphs. | Andrej Bogdanov, Kenji Obata, Luca Trevisan |
| 2002 | Auctions with Severely Bounded Communication. | Liad Blumrosen, Noam Nisan |
| 2002 | Global Information from Local Observation. | Itai Benjamini, Lszl Lovsz |
| 2002 | Breaking the O(n1/(2k-1)) Barrier for Information-Theoretic Private Information Retrieval. | Amos Beimel, Yuval Ishai, Eyal Kushilevitz, Jean-Franois Raymond |
| 2002 | Authentication of Quantum Messages. | Howard Barnum, Claude Crpeau, Daniel Gottesman, Adam D. Smith, Alain Tapp |
| 2002 | Constant-Round Coin-Tossing with a Man in the Middle or Realizing the Shared Random String Model. | Boaz Barak |
| 2002 | An Information Statistics Approach to Data Stream and Communication Complexity. | Ziv Bar-Yossef, T. S. Jayram, Ravi Kumar, D. Sivakumar |
| 2002 | Correlation Clustering. | Nikhil Bansal, Avrim Blum, Shuchi Chawla |
| 2002 | Graph Isomorphism is in SPP. | Vikraman Arvind, Piyush P. Kurur |
| 2002 | Proving Integrality Gaps without Knowing the Linear Program. | Sanjeev Arora, Bla Bollobs, Lszl Lovsz |
| 2002 | Scheduling Over a Time-Varying User-Dependent Channel with Applications to High Speed Wireless Data. | Matthew Andrews, Lisa Zhang |
| 2002 | Small Induced-Universal Graphs and Compact Implicit Graph Representations. | Stephen Alstrup, Theis Rauhe |
| 2002 | Explicit Unique-Neighbor Expanders. | Noga Alon, Michael R. Capalbo |
| 2002 | Learning a Hidden Matching. | Noga Alon, Richard Beigel, Simon Kasif, Steven Rudich, Benny Sudakov |
| 2002 | Power from Random Strings. | Eric Allender, Harry Buhrman, Michal Kouck, Dieter van Melkebeek, Detlef Ronneburger |
| 2002 | Satisfiability, Branch-Width and Tseitin Tautologies. | Michael Alekhnovich, Alexander A. Razborov |
| 2002 | Linear Diophantine Equations over Polynomials and Soft Decoding of Reed-Solomon Codes. | Michael Alekhnovich |
| 2002 | Random Lattices and a Conjectured 0 - 1 Law about Their Polynomial Time Computable Properties. | Mikls Ajtai |