List of accepted papers

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