PCP: Approaching a Polynomially-Small Error-Probability
I. Dinur and E. Fischer and G. Kindler and R. Raz and S. Safra
Computational sample complexity and attribute-efficient learning
Rocco A. Servedio
Constructions of Near-Optimal Extractors Using Pseudo-Random Generators
Luca Trevisan
Optimal Buy-and-Hold Strategies for Financial Markets with
Gen-Huey Chen and Ming-Yang Kao and Yuh-Dauh Lyuu and Hsing-Kuo Wong
A Fully Dynamic Algorithm for Maintaining Transitive Closure
Valerie King and Garry Sagert
Optimal Union-Find: Upper and Lower Bounds
Stephen Alstrup and Amir M. Ben-Amram and Theis Rauhe
Makespan Minimization in Job Shops: A Polynomial Time Approximation Scheme
Maxim I. Sviridenko
Lower Bounds for Leader Election and Collective Coin-Flipping in the Perfect Information Model
Alexander Russell and Michael Saks and David Zuckerman
An O(1)-approximation algorithm for the k-median problem
Eva Tardos and David B. Shmoys
Finding Similar Regions In Many Strings
Ming Li and Bin Ma and Lusheng Wang
Linear Gaps Between Degrees for the Polynomial Calculus Modulo Distinct Primes
Sam Buss and Russell Impagliazzo and Toniann Pitassi
Determinism versus Non-Determinism for Linear TIme RAMs with Memory
Miklos Ajtai
On the Complexity of Diophantine Geometry in Low Dimensions
J. Maurice Rojas
Algorithmic Mechanism Design
Noam Nisan and Amir Ronen
Covering Rectilinear POlygons with Axis-Parallel Rectangles
V.S.Anil Kumar and H. Ramesh
Extracting All the Randomness from a Weak Random Source
Salil P. Vadhan
A Polynomial Time Approximation Scheme for General Multiprocessor Job Scheduling
Jianer Chen and Antonio Miranda
Embedding tree metrics into low dimensional Euclidean spaces
Anupam Gupta
The quantum query complexity of approximating the median and related problems
Ashwin Nayak and Felix Wu
Complexity of Graph Partition Problems
Tomas Feder and Pavol Hell and Sulamita Klein and Rajeev Motwani
Outward rotations: a new tool for rounding solutions of semidefinite programming relaxations,
Uri Zwick
All Pairs Lightest Shortest Paths
Uri Zwick
Minimizing the Flow Time without Migration
B. Awerbuch and Y. Azar, S. Leonardi, and O. Regev
Optimal Bounds for the Predecessor Problem
Paul Beame and Faith Fich
Exponential separation of quantum and classical communication complexity
Ran Raz
A Polynomial Combinatorial Algorithm for Generalized Minimum Cost Flow
Kevin D. Wayne
Improved approximation schemes for scheduling unrelated parallel machines
Klaus Jansen and Lorant Porkolab
Short Proofs are Narrow - Resolution made Simple
Eli Ben-Sasson and Avi Wigderson
Random Sampling of Large Planar Maps and Convex Polyhedra
Gilles Schaeffer
Exploiting Regularities in Web Traffic Patterns for Cache Replacement
Edith Cohen and Haim Kaplan
Robust Logics
Leslie G Valiant
Hypergraph Isomorphism and Structural Equivalence of Boolean Functions
Eugene M. Luks
From Static to Dynamic Routing: Efficient Transformations of Store-and-Forward Protocols
Christian Scheideler and Berthold Voecking
Oblivious Transfer and Polynomial Evaluation
Moni Naor "and" Benny Pinkas
Packet Routing with Arbitrary End-to-End Delay Requirements
Matthew Andrews and Lisa Zhang
Near-Optimal Hardness Results and Approximation Algorithms for Edge-Disjoint Paths and Related Problems.
Venkatesan Guruswami and Sanjeev Khanna and Rajmohan Rajaraman and Bruce Shepherd and Mihalis Yannakakis.
Dense Quantum Coding and a Lower Bound for 1-way Quantum Automata
Andris Ambainis and Ashwin Nayak and Amnon Ta-Shma and Umesh Vazirani
Static and Dynamic Evaluation of QoS Properties
Gopal Pandurangan and Eli Upfal
Better Rounding Algorithms for a Geometric Embedding Relaxation of Minimum Multiway Cut
David R. Karger and Phil Klein and Cliff Stein and Mikkel Thorup and Neal E. Young
Small Universal Graphs
Michael R. Capalbo and S. Rao Kosaraju
A Constant Factor Approximation for the k-Median Problem
Moses Charikar and Sudipto Guha
Scheduling Data Transfers in a Network and the Set Scheduling Problem
Ashish Goel and Monika R. Henzinger and Serge Plotkin and Eva Tardos
Highly efficient PCPs for general computations
Funda Ergun and Ravi Kumar and Ronitt Rubinfeld
On targeting Markov segments
Moses Charikar and Ravi Kumar and Prabhakar Raghavan and Sridhar
Graph Nonisomorphism has Subexponential Size Proofs Unless the Polynomial-Time Hierarchy Collapses
Adam R. Klivans and Dieter van Melkebeek
Approximate Testing with Relative Error
Marcos Kiwi and Frederic Magniez and Miklos Santha
Satisfiability of word equations with constants is in NEXPTIME
Wojciech Plandowski
Sampling Fourier Transforms on Different Domains
Lisa Hales and Sean Hallgren
Backing up in Singly Linked Lists
Amir M. Ben-Amram and Holger Petersen
Bit complexity of breaking and achieving symmetry
Yefim Dinitz and Shlomo Moran and Sergio Rajsbaum
The communication complexity of pointer chasing, Applications of entropy and sampling
Stephen J. Ponzio and Jaikumar Radhakrishnan and S. Venkatesh
Designing Networks with Bounded Pairwise Distance
Yevgeniy Dodis and Sanjeev Khanna
Secure Computation with Hidden Cheaters
Ran Canetti and Rafail Ostrovsky
On the Complexity of Computing Short Linearly Independent Vectors and Short Bases in a Lattice
Jean-Pierre Seifert and Johannes Bloemer
Efficient Computation of Geodesic Shortest Paths
Sanjiv Kapoor
Pseudorandom generators without the XOR Lemma
Madhu Sudan and Luca Trevisan and Salil Vadhan
One-way Functions are Essential for Single Database Private Information Retrieval
Amos Beimel and Eyal Kushilevitz and Tal Malkin and Yuval Ishai
Undecidability on Quantum Finite Automata
Masami Amano and Kazuo Iwama
A Theorem on Sensitivity and Applications in Private Computation
Anna G/'al and Adi Ros\'{e}n
Multi-method dispatching: A geometric approach with applications to string matching problems.
P. Ferragina and S. Muthukrishnan and M. de Berg
A displacement structure approach to efficient list decoding of algebraic geometric codes
Vadim Olshevsky and Amin Shokrollahi
Approximating the Throughput of Real Time Multiple Machines Scheduling
Amotz Bar-Noy Sudipto Guha Joseph (Seffi) Naor Baruch Schieber
Efficient Recovery from Power Outages
Sudipto Guha Anna Moss Joseph (Seffi) Naor Baruch Schieber
A Good Neighbor is Hard to Find
Amit Chakrabarti and Bernard Chazelle and Benjamin Gum and Alexey Lvov
Algorithms for Testing the Uniqueness of Maximum Matchings
Harold N. Gabow and Haim Kaplan and Robert E. Tarjan
Lifting Markov Chains to Speed up Mixing
Fang Chen and Laszlo Lovasz and Igor Pak
A logarithmic Cheeger inequality and mixing in random walks
Ravi Kannan and Laszlo Lovasz
Compact Grid Layouts of Some Multi-Level Networks
S. Muthukrishnan, M. S. Paterson, S. C. Sahinalp, T. Suel
Improved Upper Bounds on Information-Theoretic Private Information Retrieval
Yuval Ishai and Eyal Kushilevitz
Subquadratic Approximation Algorithms For clusterng Problems in High Dimensional Spaces
Allan Borodin and Rafail Ostrovsky and Yuval Rabani
Molecular Scale Heat Engines and Scalable Quantum Computation
Leonard J. Schulman and Umesh Vazirani
Lower Bounds for High Dimensional Nearest Neighbor Search and
Allan Borodin and Rafail Ostrovsky and Yuval Rabani
Nonmonotonic Phenomena in Packet Routing
Uriel Feige
Scheduling in the Dark
Jeff Edmonds
Sublinear Time Algorithms for Metric Space Problems
Piotr Indyk
A PTAS for minimizing the weighted sum of job completion times on parallel machines
M. Skutella and G.J. Woeginger
Interpolation of Symmetric Functions and a New Type of Combinatorial Design
Piotr Indyk
Hardness and Hierarchy Theorems for Probabilistic Time
Jin-Yi Cai and Ajay Nerurkar and D.Sivakumar
Chinese Remaindering with Errors
Oded Goldreich and Dana Ron and Madhu Sudan
Approximation schemes for minimum latency problems.
Sanjeev Arora and George Karakostas.
Solution of Matrix Eigenproblem via Polynomial Rootfinders
Victor Y. Pan and z.chen
Security-Preserving Hardness-Amplification for Any Regular One-Way Function
Giovanni Di Crescenzo and Russell Impagliazzo
Majorizing estimators and the approximation of #P-complete problems
Leonard J. Schulman and Vijay V. Vazirani
On recycling the randomness of the states in space bounded computation
Ran Raz, Omer Reingold
Stability of Adaptive and Non-Adaptive Packet Routing Policies
David Gamarnik
Connection Caching
Edith Cohen and Haim Kaplan and Uri Zwick
Graph Ramsey Theory and the Polynomial Hierarchy
Marcus Schaefer