Lovasz's Lemma for the K-Level of Concave Surfaces and its Applications Naoki Katoh and Takeshi Tokuyama A Non-linear Time Lower Bound for Boolean Branching Programs Miklos Ajtai Efficient testing of large graphs Noga Alon and Eldar Fischer and Michael Krivelevich and Mario Szegedy Setting Parameters by Example David Eppstein Lower Bounds for the Rank of Matrix Multiplication Markus Blaeser Reducing Randomness via Chinese Remaindering Manindra Agrawal and Somenath Biswas A probabilistic algorithm for k-SAT and constraint satisfaction problems Uwe Sch"oning Derandomizing Arthur-Merlin Games using Hitting Sets Peter Bro Miltersen and N.V. Vinodchandran A near-tight lower bound on the time complexity of distributed MST construction D. Peleg and V. Rubinovich A Study of Proof Search Algorithms for Resolution etc Maria Bonet and Nicola Galesi PSPACE has constant-round quantum interactive proof systems John Watrous Improved Bounds for Sampling Colorings Eric Vigoda Random CNF's are Hard for the Polynomial Calculus Eli Ben-Sasson and Russell Impagliazzo Noncryptographic Selection Protocols Uriel Feige Cuts, Trees and l_1-Embeddings of Graphs Anupam Gupta and Ilan Newman and Yuri Rabinovich and Alistair Sinclair Finding Double Euler Trails of Planar Graphs in Linear Time Zhi-Zhong Chen and Xin He and Chun-Hsi Huang Approximation Schemes for Scheduling to Minimize Average Weighted Completion Time with Release Dates C. Chekuri and D. Karger and S. Khanna and M. Skutella and C. Stein F. Afrati and E. Bampis and C. Kenyon and I. Milis Reducing Network Congestion and Blocking Probability Through Balanced Allocation Malwina L. Luczak and Eli Upfal All Pairs Shortest Paths in Undirected Graphs with Integer Weights Avi Shoshan and Uri Zwick Dynamic planar convex hull operations in near-logarithmic amortized time Timothy M. Chan Approximating fractional multicommodity flow independent of the number of commodities Lisa K. Fleischer Limits on the Efficiency of One-Way Permutation-Based Hash Functions Jeong Han Kim and Daniel R. Simon and Prasad Tetali Cache-Oblivious Algorithms Matteo Frigo and Charles E. Leiserson and Harald Prokop and Sridhar Ramachandran Approximation Algorithms for Classification Problems with Pairwise Relationships: Metric Labeling and Markov Random Fields Jon Kleinberg and Eva Tardos Near-Optimal conversion of Hardness into Pseudo-Randomness Russell Impagliazzo and Ronen Shaltiel and Avi Wigderson Taking a walk in a planar arrangement Sariel Har-Peled Markovian Coupling is not powerful as Conductance V.S. Anil Kumar and H. Ramesh Fairness in Routing and Load Balancing Jon Kleinberg and Yuval Rabani and Eva Tardos Algorithmic theories of learning Rosa I. Arriaga and Santosh Vempala Fully Dynamic Algorithms for Maintaining All-Pairs Shortest Paths and Transitive Closure in Digraphs Valerie King On counting independent sets in sparse graphs Martin Dyer and Alan Frieze and Mark Jerrum How Asymmetry Helps Load Balancing B. Voecking A Theoretical Framework for Memory-Adaptive Algorithms Rakesh D. Barve and Jeffrey Scott Vitter Learning mixtures of Gaussians Sanjoy Dasgupta Non-Malleable Non-Interactive Zero Knowledge and Achieving Chosen-Ciphertext Security Amit Sahai Boosting and Hardness Amplification Adam R. Klivans and Rocco A. Servedio The Directed Steiner Network problem is tractable for a constant number of terminals Jon Feldman and Matthias Ruhl Primal-Dual Approximation Algorithms for Metric Facility Location and k-Median Problems Kamal Jain and Vijay V. Vazirani Random walks on truncated cubes and sampling 0-1 knapsack solutions Ben Morris and Alistair Sinclair Hardness of Approximating Sigma_2^p Minimization Problems Christopher Umans On Universal and Fault-Tolerant Quantum Computing: A Novel Basis and a New Constructive Proof of Universality for Shor's Basis P. Oscar Boykin and Tal Mor and Mathew Pulver and Vwani Roychowdhury and Farrokh Vatan Edge-Disjoint Routing in Plane Switch Graphs in Linear Time Karsten Weihe Optimal lower bounds for quantum automata and random access codes Ashwin Nayak Finding Maximal Repetitions in a Word in Linear Time Kolpakov, Roman and Kucherov, Gregory Reducing Error Probability in Quantum Algorithms H. Buhrman and R. Cleve and R. de Wolf and Ch. Zalka Satisfiability of Word Equations with Constants is in PSPACE Wojciech Plandowski Hardness of Approximating the Minimum Distance of a Linear Code Ilya Dumer and Daniele Micciancio and Madhu Sudan Verifiable Random Functions Silvio Micali and Michael Rabin and Salil Vadhan Error Reduction for Extractors Ran Raz and Omer Reingold and Salil Vadhan Approximate Nearest Neighbor Algorithms for Hausdorff Metrics via Embeddings Martin Farach-Colton and Piotr Indyk Scheduling to Minimize Average Stretch Johannes E. Gehrke and S. Muthukrishnan and Rajmohan Rajaraman and Anthony Shaheen Torpid Mixing of Some Monte Carlo Markov Chain Algorithms in Statistical Physics Christian Borgs and Jennifer Chayes and Alan Frieze and Jeong Han Kim and Prasad Tetali and Eric Vigoda and Van Ha Vu On the Complexity of SAT Richard J Lipton and Anastasios Viglas An Approximate L1-Difference Algorithm for Massive Data Streams J. Feigenbaum and S. Kannan and M. Strauss and M. Viswanathan Long-Lived and Adaptive Collect with Applications Y. Afek and G. Stupp and D. Touitou A better lower bound for quantum algorithms searching an ordered list Andris Ambainis Finely-competitive paging Avrim Blum and Carl Burch and Adam Kalai On quantum and classical space-bounded processes with algebraic transition amplitudes John Watrous Non-Interactive CryptoComputing For NC1 Tomas Sander and Adam Young and Moti Yung Stochastic Load Balancing and Related Problems Ashish Goel and Piotr Indyk Improved Combinatorial Algorithms for the Facility Location and k-Median Problems Moses Charikar and Sudipto Guha Magic Functions Dwork and Naor and Reingold and Stockmeyer Algorithmic Aspects of Protein Structure Similarity Deborah Goldman and Sorin Istrail and Christos H. Papadimitriou Weak adversaries for the k-server problem Elias Koutsoupias A PTAS for Clustering in Metric Spaces Piotr Indyk Efficient Regular Data Structures and Algorithms for Location and Proximity Problems Arnon Amir and Alon Efrat and Piotr Indyk and Hanan Samet Regular Languages Are Testable With a Constant Number of Queries Noga Alon, Michael Krivelevich, Ilan Newman, Mario Szegedy