Unsatisfiable systems of equations, over a finite field. --- Alan R. Woods Multiplicative Complexity of Taylor Shifts and a New Twist of the Substitution Method --- Arnold Schoenhage Bivariate Polynomial Multiplication --- Markus Blaeser Exponential Complexity Lower Bounds for Depth 3 Arithmetic Circuits in Algebras of Functions Over Finite Fields --- Dima Grigoriev and Alexander Razborov Local Search in Smooth Convex Sets --- Ravi Kannan and Andreas Nolte Algorithms to Tile the Infinite Grid with Finite Clusters --- Mario Szegedy On the single-source unsplittable flow problem --- Yefim Dinitz and Naveen Garg and Michel Goemans Random Sampling, Halfspace Range Reporting, and Construction of $(\le k)$-Levels in Three Dimensions --- Timothy M. Chan Perfect Information Leader Election in log^* n + O(1) Rounds --- Alexander Russell and David Zuckerman Delayed Information and Action in Online Algorithms --- Susanne Albers and Moses Charikar and Michael Mitzenmacher The Shortest Vector in a Lattice is Hard to Approximate to within Some Constant --- Daniele Micciancio The Security of Individual RSA Bits --- Johan Håstad and Mats Näslund Fast Monte-Carlo Algorithms for finding low-rank approximations --- Alan Frieze and Ravi Kannan and Santosh Vempala Evolutionary Trees can be Learned in Polynomial Time in the Two-State --- Mary Cryan and Leslie Ann Goldberg and Paul W. Goldberg Decidability of bisimulation equivalence for equational graphs of finite out-degree --- Geraud Senizergues All Pairs Shortest Paths in weighted directed graphs -- exact and almost exact algorithms --- Uri Zwick Semidefinite Relaxations for Parallel Machine Scheduling --- Martin Skutella Map Graphs in Polynomial Time --- Mikkel Thorup A TDI System and Its Application to Approximation Algorithms --- Mao-cheng Cai and Xiaotie Deng and Wenan Zang Optimal Time-Space Trade-offs for Sorting --- Jakob Pagter and Theis Rauhe Exponential Separations between Restricted Resolution and Cutting Planes Proof Systems --- Maria Luisa Bonet and Juan Luis Esteban and Nicola Galesi and Jan Johannsen Which Problems have Strongly Exponential Complexity? --- Russell Impagliazzo and Ramamohan Paturi and Francis Zane The Quantum Communication Complexity of Sampling --- Andris Ambainis and Leonard Schulman and Amnon Ta-Shma and Umesh Vazirani and Avi Wigderson Marked Ancestor Problems --- Stephen Alstrup and Thore Husfeldt and Theis Rauhe Approximating a Finite Metric by a Small Number of Tree Metrics --- M. Charikar and C. Chekuri and A. Goel and S. Guha and S. Plotkin Lower Bounds for (MOD p, MOD m) Circuits --- Vince Grolmusz and Gabor Tardos Testing Monotonicity --- Oded Goldreich and Shafi Goldwasser and Eric Lehman and Dana Ron The Minimum Equivalent DNF Problem and Shortest Implicants --- Christopher Umans Geometric separator theorems and applications --- Warren D. Smith and Nick Wormald The Access Network Design Problem --- Matthew Andrews and Lisa Zhang On the Combinatorial and Topological Complexity of a Single Cell --- Saugata Basu A Linguistic Characterization of Bounded Oracle Computation and Probabilistic Polynomial Time --- J. Mitchell and M. Mitchell and A. Scedrov Recommendation Systems: A Probabilistic Analysis --- S Ravi Kumar and Prabhakar Raghavan and Sridhar Rajagopalan and Andrew Tomkins Approximating CVP to within almost-polynomial factors is NP-hard --- Irit Dinur and Guy Kindler and Shmuel Safra Heuristics for finding large independent sets, with applications to coloring semi-random graphs --- Uri Feige and Joe Kilian Oblivious Transfer with a Memory-Bounded Receiver --- Christian Cachin and Claude Crepeau and Julien Marcil A divide-and-conquer algorithm for Euclidean min-cost perfect matching --- Kasturi R. Varadarajan A Tight Characterization of NP with 3 Query PCPs --- Venkatesan Guruswami and Daniel Lewin and Madhu Sudan and Luca Trevisan Probabilistically Checkable Proofs with Low Amortized Query Complexity --- Madhu Sudan and Luca Trevisan Approximation of Radii and Norm-Maxima: No Need to Randomize --- Andreas Brieden and Peter Gritzman and Ravi Kannan and Victor Klee and Laszlo Lovasz and Miklos Simonovits. The Complexity of Acyclic Conjunctive Queries --- G. Gottlob and N. Leone and F. Scarcello The Finite Capacity Dial-A-Ride Problem --- Moses Charikar and Balaji Raghavachari A Factor 2 Approximation Algorithm for the Generalized Steiner Network Problem --- Kamal Jain 1-way quantum finite automata: strengths, weaknesses and generalizations --- Andris Ambainis and Rusins Freivalds Which crossing number is it, anyway? --- J\'anos Pach and G\'eza T\'oth Improved bounds and algorithms for hypergraph two-coloring --- Jaikumar Radhakrishnan and Aravind Srinivasan Satisfiability of Word Equations with Constants is in Exponential Space --- Claudio Gutierrez Improved Decoding of Reed-Solomon and Algebraic-Geometric Codes --- Venkatesan Guruswami and Madhu Sudan Faster and Simpler Algorithms for Multicommodity Flow and other Fractional Packing Problems --- Naveen Garg and Jochen Koenemann The Complexity of the Approximation of the Bandwidth Problem --- Walter Unger Randomness vs. Time: De-randomization under a uniform assumption --- Russell Impagliazzo and Avi Wigderson Faster algorithms for string matching problems: matching the convolution bound --- Piotr Indyk On Approximate Nearest Neighbors in Non-Euclidean Spaces --- Piotr Indyk Jitter Control in QoS networks --- Yishay Mansour and Boaz Patt-Shamir Pattern Matching for Spatial Point Sets --- Leonard Schulman and David Cardoze Random Projection: a new approach to VLSI layout. --- Santosh Vempala Quantum Cryptography with Imperfect Apparatus --- Dominic Mayers and Andrew Yao An Improved Exponential-time Algorithm for $k$-SAT --- Ramamohan Paturi and Pavel Pudlak and Mike Saks and Francis Zane Overcoming the memory bottleneck in suffix tree construction --- M. Farach and P. Ferragina and S. Muthukrishnan Time-Space Tradeoffs for Branching Programs --- Paul Beame and Michael Saks and Jayram S. Thathachar Local Divergence of Markov Chains and the Analysis of Iterative Load Balancing Schemes --- Yuval Rabani and Alistair Sinclair and Rolf Wanka A Primitive Recursive Algorithm for the General Petri Net --- Zakaria Bouziane Parametric and Kinetic Minimum Spanning Trees --- Pankaj K. Agarwal and David Eppstein and Leonidas J. Guibas and Monika R. Henzinger Stability of Adversarial Queues via Fluid Models --- David Gamarnik Protocols for Asymmetric Communication Channels --- Micah Adler and Bruce Maggs Orchestrating Quartets: Approximation and Data Correction --- Tao Jiang and Paul Kearney and Ming Li Quantum Lower Bounds by Polynomials --- R. Beals and H. Buhrman and R. Cleve and M. Mosca and R. de Wolf Concurrent Reachability Games --- Luca de Alfaro and Thomas A. Henzinger and Orna Kupferman Zero Knowledge on the Internet --- Joe Kilian and Erez Petrank and Charlie Rackoff A superfast state-space algorithm for tangential Nevanlinna-Pick interpolation problem --- Vadim Olshevsky and Victor Pan On learning monotone Boolean functions --- Avrim Blum and Carl Burch and John Langford Tseitin's Tautologies and Lower Bounds for Nullstellensatz Proofs --- Dima Grigoriev A Randomized Approximation Scheme for Euclidean MAX-CUT --- W. Fernandez de la Vega and C. Kenyon Towards an Optimal Bit-Reversal Permutation Program --- Larry Carter and Kang Su Gatlin A characterization of NC by tree recurrence --- Daniel Leivant Quantum Oracle Interrogation: Getting all information for almost half the price --- Wim van Dam