A Complete Classification of the Approximability of Maximization Problems Derived from Boolean Constraint Satisfaction, by Sanjeev Khanna, Madhu Sudan and David P. Williamson
A Composition Theorem for Learning Algorithms with Applications to Geometric Concept Classes, by S. Ben-David, N. Bshouty and E. Kushilevitz
A Constant-Factor Approximation Algorithm for Packet Routing, and Balancing Local vs. Global Criteria, by Aravind Srinivasan and Chung-Piaw Teo
A Public-Key Cryptosystem with Worst-Case/Average-Case Equivalence, by Miklos Ajtai and Cynthia Dwork
A polylog(n)-competitive algorithm for metrical task systems, by Yair Bartal, Avrim Blum, Carl Burch and Andrew Tomkins
A Sub-Constant Error-Probability Low-Degree test and a Sub-Constant Error-Probability PCP Characterization of NP by Ran Raz and Shmuel Safra
All of us are smarter than any of us: more on the robustness of the Consensus hierarchy, by Wai-Kau Lo and Vassos Hadzilacos
Allocating Bandwidth for Bursty Connections, by Jon Kleinberg, Yuval Rabani and Eva Tardos
An algorithm, unbiased for user impatience, for exact sampling via Markov chains, by James Fill
Approximate Complex Polynomial Evaluation in Near Constant Work Per Point, by John H. Reif
Approximating Total Flow Time on Parallel Machines, by Stefano Leonardi and Danny Raz
Approximating hyper-rectangles: learning and pseudo-random sets, by Peter Auer, Philip M. Long and Aravind Srinivasan
Approximation algorithms for facility location problems, by Karen Aardal, David B. Shmoys and Eva Tardos
Approximation of k-Set Cover by Semi-Local Optimization, by Rong-chii Duh and Martin Furer
Better Bounds for Online Scheduling, by Susanne Albers
Byzantine Quorum Systems, by Dahlia Malkhi and Michael Reiter
Combinatorial Complexity of the Central Curve, by Peter A. Beling and Sushil Verma
Commodity-Based Cryptography, by Donald Beaver
Computationally Private Information Retrieval, by Benny Chor and Niv Gilboa
Covering points in the plane by k-tours: towards a polynomial time approximation scheme for general k, by Tetsuo Asano, Naoki Katoh, Hisao Tamaki and Takeshi Tokuyama
Direct Product Results and the GCD Problem, in Old and New Communication Models, by I. Parnafes, R. Raz and A. Wigderson
Efficient Algorithms for Comparing Unrooted Evolutionary Trees by Ming-Yang Kao, Tak Wah Lam, Teresa Przytycka, Wing Kin Sung and Hing Fung Ting
Exploring Unknown Environments, by Susanne Albers and Monika Henzinger
Exponential Lower Bounds for Depth 3 Boolean Circuits, by Ramamohan Paturi, Michael E. Saks and Francis Zane
Fast and Precise Computations of Discrete Fourier Transforms using Cyclotomic Integers, by Joe Buhler, Amin Shokrollahi and Volker Stemann
Fault Tolerant Quantum Computation With Constant Error, by D. Aharonov and M. Ben-Or
Hamming Spaces, Euclid Spaces, and the Non-Approximability of Geometric TSP and MST, by Luca Trevisan
Improved Low Degree Testing and its Applications, by Sanjeev Arora and Madhu Sudan
Improved Pade approximation approach to decoding error-correcting codes, by Victor Y. Pan
Improved Routing and Sorting on Multibutterflies, by Bruce M. Maggs and Berthold Voecking
Incremental Clustering and Dynamic Information Retrieval, by Moses Charikar, Chandra Chekuri, Tomas Feder and Rajeev Motwani
Is $P \not = NC$ hard or unprovable? by Ketan Mulmuley
Linear Hashing Yields Small Buckets, by Noga Alon, Martin Dietzfelbinger, Peter Bro Miltersen, Erez Petrank and G\'abor Tardos
Linear Zero-Knowledge, by Ivan Damgaard and Ronald Cramer
Locality-Preserving Hashing in Multidimensional Spaces, by Piotr Indyk, Rajeev Motwani, Prabhakar Raghavan and Santosh Vempala
Lower bounds for distributed coin-flipping and randomized consensus, by James Aspnes
Making Games Short, by Uri Feige and Joe Kilian
Nearest Neighbor Queries in Metric Spaces, by Kenneth L. Clarkson
Non-Clairvoyant Multiprocessor Scheduling of Jobs with Changing Execution Characteristics, by J. Edmonds, D. Chinn, T. Brecht, and X. Deng
Oblivious Data Structures: Applications to Cryptography, by Daniele Micciancio
On ACC0[p^k] Frege proofs, by Alexis Maciel and Toniann Pitassi
On Approximately Counting Independent Sets, by Michael Luby and Eric Vigoda
On Floor Plan of Planar Graphs, by Xin He
On Sorting Strings in External Memory, by Lars Arge, Paolo Ferragina, Roberto Grossi and Jeffrey S. Vitter
On the Construction of Pseudo-Random Permutations: Luby-Rackoff Revisited, by Moni Naor and Omer Reingold
On-line Algorithms for Steiner Tree Problems, by Piotr Berman and Chris Coulston
Online Algorithms for Selective Multicast and Maximal Dense Trees, by Baruch Awerbuch and Tripurari Singh
Optimal time-critical scheduling via resource augmentation, by Cynthia Phillips, Cliff Stein, Eric Torng and Joel Wein
$P=BPP$ unless $E$ has sub-exponential circuits, by Russell Impagliazzo and Avi Wigderson
Page replacement with multi-size pages and applications to web caching, by Sandy Irani
Permanents, Pfaffian orientations, and even directed circuits, by William McCuaig, Neil Robertson, Paul Seymour and Robin Thomas
Pointer Jumping Requires Concurrent Read, by Noam Nisan and Ziv Bar-Yossef
Practical Erasure-Resilient Codes, by Michael Luby, Michael Mitzenmacher, Amin Shokrollahi, Daniel Spielman and Volker Stemann
Private Information Storage, by Rafail Ostrovsky and Victor Shoup
Probabilistically Checkable Proofs with Zero Knowledge, by Joe Kilian, Erez Petrank and Gabor Tardos
Property Testing in Bounded Degree Graphs, by Oded Goldreich and Dana Ron
Quantum computation of Fourier transforms over symmetric groups, by Robert Beals
Randomized $\Omega (n^2)$ Lower Bound for Knapsack, by Dima Grigoriev and Marek Karpinski
Read-once branching programs, rectangular proofs of the pigeonhole principle, and the transversal calculus, by A. Razborov, A. Wigderson and A. Yao
Reducing Randomness via Irrational Numbers, by Zhi-Zhong Chen and Ming-Yang Kao
Reductions in Complexity Theory: An Isomorphism Theorem and a Gap Theorem, by Agrawal, Allender, Impagliazzo, Pitassi and Rudich
Relieving Hot Spots on the World Wide Web, by David Karger, Eric Lehman, Daniel Lewin, Matt Levine, Tom Leighton and Rina Panigrahy
Sampling Lattice Points, by Ravi Kannan and Santosh Vempala
$SL \subseteq L^{\frac{4}{3}}$, by Roy Armoni, Amnon Ta-Shma, Avi Wigderson and Shiyu Zhou
Some optimal inapproximability results, by Johan Hastad
Spectral Techniques for Expander Codes, by John Lafferty and Daniel Rockmore
Static and Dynamic Path Selection on Expander Graphs: A Random Walk Approach, by Andrei Z. Broder, Alan M. Frieze and Eli Upfal
The Decidability of Distributed Decision Tasks, by Maurice Herlihy and Sergio Rajsbaum
The Linear-Array Problem in Communication Complexity Resolved, by Martin Dietzfelbinger
The Swendsen-Wang process does not always mix rapidly, by Vivek K. Gore and Mark R. Jerrum
Theory and applications of predictors that specialize, by Yoav Freund, Robert E. Schapire, Yoram Singer and Manfred K. Warmuth
Tree Pattern Matching and Subset Matching in Randomized O(n log^3n) Time, by Richard Cole and Ramesh Hariharan
Two Algorithms for Nearest-Neighbor Search in High Dimensions, by Jon M. Kleinberg
Universal O(congestion+dilation+\log^{1+\eps} N) local control packet switching algorithms, by Rafail Ostrovsky and Yuval Rabani
Using Random Sampling to Find Maximum Flows in Uncapacitated Graphs, by David Karger