| 2002 | 43rd Symposium on Foundations of Computer Science, FOCS 2002, Vancouver, BC, Canada, November 16-19, 2002, Proceedings |
| 2002 | A Constant-Factor Approximation Algorithm for the Multicommodity Rent-or-Buy Problem. Amit Kumar, Anupam Gupta, Tim Roughgarden |
| 2002 | A Dichotomy Theorem for Constraints on a Three-Element Set. Andrei A. Bulatov |
| 2002 | A Lower Bound for Testing 3-Colorability in Bounded-Degree Graphs. Andrej Bogdanov, Kenji Obata, Luca Trevisan |
| 2002 | A Simple Algorithmic Characterization of Uniform Solvability. Eli Gafni |
| 2002 | A Spectral Algorithm for Learning Mixtures of Distributions. Santosh S. Vempala, Grant Wang |
| 2002 | A Switching Lemma for Small Restrictions and Lower Bounds for k - DNF Resolution. Nathan Segerlind, Samuel R. Buss, Russell Impagliazzo |
| 2002 | Abstract Combinatorial Programs and Efficient Property Testers. Artur Czumaj, Christian Sohler |
| 2002 | An Information Statistics Approach to Data Stream and Communication Complexity. Ziv Bar-Yossef, T. S. Jayram, Ravi Kumar, D. Sivakumar |
| 2002 | An Inverse-Ackermann Style Lower Bound for the Online Minimum Spanning Tree. Seth Pettie |
| 2002 | Auctions with Severely Bounded Communication. Liad Blumrosen, Noam Nisan |
| 2002 | Authentication of Quantum Messages. Howard Barnum, Claude Crépeau, Daniel Gottesman, Adam D. Smith, Alain Tapp |
| 2002 | Bounded-Depth Frege Lower Bounds for Weaker Pigeonhole Principles. Josh Buresh-Oppenheim, Paul Beame, Toniann Pitassi, Ran Raz, Ashish Sabharwal |
| 2002 | Breaking the O(n1/(2k-1)) Barrier for Information-Theoretic Private Information Retrieval. Amos Beimel, Yuval Ishai, Eyal Kushilevitz, Jean-François Raymond |
| 2002 | Concurrent Zero Knowledge with Logarithmic Round-Complexity. Manoj Prabhakaran, Alon Rosen, Amit Sahai |
| 2002 | Conflict-Free Colorings of Simple Geometric Regions with Applications to Frequency Assignment in Cellular Networks. Guy Even, Zvi Lotker, Dana Ron, Shakhar Smorodinsky |
| 2002 | Constant-Round Coin-Tossing with a Man in the Middle or Realizing the Shared Random String Model. Boaz Barak |
| 2002 | Correlation Clustering. Nikhil Bansal, Avrim Blum, Shuchi Chawla |
| 2002 | Covering Problems with Hard Capacities. Julia Chuzhoy, Joseph Naor |
| 2002 | Decoding Turbo-Like Codes via Linear Programming. Jon Feldman, David R. Karger |
| 2002 | Dependent Rounding in Bipartite Graphs. Rajiv Gandhi, Samir Khuller, Srinivasan Parthasarathy, Aravind Srinivasan |
| 2002 | Deterministic Broadcasting Time in Radio Networks of Unknown Topology. Dariusz R. Kowalski, Andrzej Pelc |
| 2002 | Dimension Reduction in the \ell _1 Norm. Moses Charikar, Amit Sahai |
| 2002 | Dynamic Planar Convex Hull. Gerth Stølting Brodal, Riko Jacob |
| 2002 | Equivalence between Priority Queues and Sorting. Mikkel Thorup |
| 2002 | Erratum to "Vickrey Pricing and Shortest Paths: What is an Edge Worth?". John Hershberger, Subhash Suri |
| 2002 | Explicit Unique-Neighbor Expanders. Noga Alon, Michael R. Capalbo |
| 2002 | Fast Approximation Algorithms for Fractional Steiner Forest and Related Problems. Naveen Garg, Rohit Khandekar |
| 2002 | Forbidden Information. Leonid A. Levin |
| 2002 | Generalized Compact Knapsacks, Cyclic Lattices, and Efficient One-Way Functions from Worst-Case Complexity Assumptions. Daniele Micciancio |
| 2002 | Global Information from Local Observation. Itai Benjamini, László Lovász |
| 2002 | Graph Isomorphism is in SPP. Vikraman Arvind, Piyush P. Kurur |
| 2002 | Graphs with Tiny Vector Chromatic Numbers and Huge Chromatic Numbers. Uriel Feige, Michael Langberg, Gideon Schechtman |
| 2002 | Hardness Results for Coloring 3 -Colorable 3 -Uniform Hypergraphs. Subhash Khot |
| 2002 | Implicit B-Trees: New Results for the Dictionary Problem. Gianni Franceschini, Roberto Grossi, J. Ian Munro, Linda Pagli |
| 2002 | Improved Dynamic Reachability Algorithms for Directed Graphs. Liam Roditty, Uri Zwick |
| 2002 | Integer Sorting in 0(n sqrt (log log n)) Expected Time and Linear Space. Yijie Han, Mikkel Thorup |
| 2002 | Kolmogorov's Structure Functions with an Application to the Foundations of Model Selection. Nikolai K. Vereshchagin, Paul M. B. Vitányi |
| 2002 | LT Codes. Michael Luby |
| 2002 | Learning Intersections and Thresholds of Halfspaces. Adam R. Klivans, Ryan O'Donnell, Rocco A. Servedio |
| 2002 | Learning a Hidden Matching. Noga Alon, Richard Beigel, Simon Kasif, Steven Rudich, Benny Sudakov |
| 2002 | Linear Diophantine Equations over Polynomials and Soft Decoding of Reed-Solomon Codes. Michael Alekhnovich |
| 2002 | Load Balancing with Memory. Michael Mitzenmacher, Balaji Prabhakar, Devavrat Shah |
| 2002 | Locally Testable Codes and PCPs of Almost-Linear Length. Oded Goldreich, Madhu Sudan |
| 2002 | Low-Dimensional Linear Programming with Violations. Timothy M. Chan |
| 2002 | Lower Bounds on the Bounded Coefficient Complexity of Bilinear Maps. Peter Bürgisser, Martin Lotz |
| 2002 | Market Equilibrium via a Primal-Dual-Type Algorithm. Nikhil R. Devanur, Christos H. Papadimitriou, Amin Saberi, Vijay V. Vazirani |
| 2002 | Minimizing Congestion in General Networks. Harald Räcke |
| 2002 | Nash Equilibria in Competitive Societies, with Applications to Facility Location, Traffic Routing and Auctions. Adrian Vetta |
| 2002 | On Approximating the Radii of Point Sets in High Dimensions. Kasturi R. Varadarajan, Srinivasan Venkatesh, Jiawei Zhang |
| 2002 | On Random Symmetric Travelling Salesman Problems. Alan M. Frieze |
| 2002 | On the (non)Universality of the One-Time Pad. Yevgeniy Dodis, Joel Spencer |
| 2002 | On the Decidability of Self-Assembly of Infinite Ribbons. Leonard M. Adleman, Jarkko Kari, Lila Kari, Dustin Reishus |
| 2002 | On the Hardness of Optimal Auctions. Amir Ronen, Amin Saberi |
| 2002 | On-Line Confidence Machines Are Well-Calibrated. Vladimir Vovk |
| 2002 | On-Line End-to-End Congestion Control. Naveen Garg, Neal E. Young |
| 2002 | Optimal System of Loops on an Orientable Surface. Éric Colin de Verdière, Francis Lazarus |
| 2002 | PAC = PAExact and Other Equivalent Models in Learning. Nader H. Bshouty, Dmitry Gavinsky |
| 2002 | Packing 2-Dimensional Bins in Harmony. Alberto Caprara |
| 2002 | Power from Random Strings. Eric Allender, Harry Buhrman, Michal Koucký, Dieter van Melkebeek, Detlef Ronneburger |
| 2002 | Privacy and Interaction in Quantum Communication Complexity and a Theorem about the Relative Entropy of Quantum States. Rahul Jain, Jaikumar Radhakrishnan, Pranab Sen |
| 2002 | Protocols and Impossibility Results for Gossip-Based Communication Mechanisms. David Kempe, Jon M. Kleinberg |
| 2002 | Proving Integrality Gaps without Knowing the Linear Program. Sanjeev Arora, Béla Bollobás, László Lovász |
| 2002 | Quantum Computation and Lattice Problems. Oded Regev |
| 2002 | Quantum Lower Bounds for the Collision and the Element Distinctness Problems. Yaoyun Shi |
| 2002 | Random Lattices and a Conjectured 0 - 1 Law about Their Polynomial Time Computable Properties. Miklós Ajtai |
| 2002 | Randomness Extractors and their Many Guises. Salil P. Vadhan |
| 2002 | Rapidly Mixing Markov Chains for Sampling Contingency Tables with a Constant Number of Rows. Mary Cryan, Martin E. Dyer, Leslie Ann Goldberg, Mark Jerrum, Russell A. Martin |
| 2002 | Satisfiability, Branch-Width and Tseitin Tautologies. Michael Alekhnovich, Alexander A. Razborov |
| 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 | Spectral Gap and log-Sobolev Constant for Balanced Matroids. Mark Jerrum, Jung-Bae Son |
| 2002 | Static Optimality Theorem for External Memory String Access. Valentina Ciriani, Paolo Ferragina, Fabrizio Luccio, S. Muthukrishnan |
| 2002 | Testing Juntas. Eldar Fischer, Guy Kindler, Dana Ron, Shmuel Safra, Alex Samorodnitsky |
| 2002 | The 3-XORSAT Threshold. Olivier Dubois, Jacques Mandler |
| 2002 | The Asymptotic Order of the Random k -SAT Threshold. Dimitris Achlioptas, Cristopher Moore |
| 2002 | The Hardness of 3 - Uniform Hypergraph Coloring. Irit Dinur, Oded Regev, Clifford D. Smyth |
| 2002 | The Parameterized Complexity of Counting Problems. Jörg Flum, Martin Grohe |
| 2002 | The Partition Technique for Overlays of Envelopes. Vladlen Koltun, Micha Sharir |
| 2002 | Zero-Knowledge. Oded Goldreich |
| 2002 | imits on the Power of Quantum Statistical Zero-Knowledge. John Watrous |