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