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