| Foreword |
| Committees |
| Machtey Award |
| Reviewers |
| Primal-Dual Approximation Algorithms for Metric Facility Location and k-Median Problems / K. Jain ; V. V. Vazirani |
| Approximation Algorithms for Classification Problems with Pairwise Relationships: Metric Labeling and Markov Random Fields / J. Kleinberg ; E. Tardos |
| Approximating Fractional Multicommodity Flow Independent of the Number of Commodities / L. K. Fleischer |
| Approximation Schemes for Minimizing Average Weighted Completion Time with Release Dates / F. Afrati ; E. Bampis ; C. Chekuri ; D. Karger ; C. Kenyon ; S. Khanna ; I. Milis ; M. Queyranne ; M. Skutella ; C. Stein ; M. Sviridenko |
| A 5/2n[superscript 2]-Lower Bound for the Rank of nxn-Matrix Multiplication over Arbitrary Fields / M. Blaser |
| Improved Bounds for Sampling Colorings / E. Vigoda |
| A Non-linear Time Lower Bound for Boolean Branching Programs / M. Ajtai |
| Derandomizing Arthur-Merlin Games Using Hitting Sets / P. Bro Miltersen ; N. V. Vinodchandran |
| Fully Dynamic Algorithms for Maintaining All-Pairs Shortest Paths and Transitive Closure in Digraphs / V. King |
| Knuth Prize Lecture / Laszlo Lovasz |
| Dynamic Planar Convex Hull Operations in Near-Logarithmic Amortized Time / T. M. Chan |
| Taking a Walk in a Planar Arrangement / S. Har-Peled |
| PSPACE Has Constant-round Quantum Interactive Proof Systems / J. Watrous |
| Verifiable Random Functions / S. Micali ; M. Rabin ; S. Vadhan |
| How Asymmetry Helps Load Balancing / B. Vocking |
| Noncryptographic Selection Protocols / U. Feige |
| A Sublinear Time Approximation Scheme for Clustering in Metric Spaces / P. Indyk |
| Efficient Regular Data Structures and Algorithms for Location and Proximity Problems / A. Amir ; A. Efrat ; H. Samet |
| Approximate Nearest Neighbor Algorithms for Hausdorff Metrics via Embeddings / M. Farach-Colton |
| Near-Optimal Conversion of Hardness into Pseudo-Randomness / R. Impagliazzo ; R. Shaltiel ; A. Wigderson |
| Error Reduction for Extractors / R. Raz ; O. Reingold |
| Primality and Identity Testing Via Chinese Remaindering / M. Agrawal ; S. Biswas |
| On Counting Independent Sets in Sparse Graphs / M. Dyer ; A. Frieze ; M. Jerrum |
| Torpid Mixing of Some Monte Carlo Markov Chain Algorithms in Statistical Physics / C. Borgs ; J. Chayes ; J. H. Kim ; P. Tetali ; V. H. Vu |
| Random Walks on Truncated Cubes and Sampling 0-1 Knapsack Solutions / B. Morris ; A. Sinclair |
| Markovian Coupling vs. Conductance for the Jerrum-Sinclair Chain / V.S. Anil Kumar ; H. Ramesh |
| A Near-Tight Lower Bound on the Time Complexity of Distributed MST Construction / D. Peleg ; V. Rubinovich |
| Long-lived Adaptive Collect with Applications / Y. Afek ; G. Stupp ; D. Touitou |
| A Theoretical Framework for Memory-Adaptive Algorithms / R. D. Barve ; J. S. Vitter |
| Cache-Oblivious Algorithms / M. Frigo ; C. E. Leiserson ; H. Prokop ; S. Ramachandran |
| The Directed Steiner Network Problem is Tractable for a Constant Number of Terminals / J. Feldman ; M. Ruhl |
| Setting Parameters by Example / D. Eppstein |
| Finding Double Euler Trails of Planar Graphs in Linear Time / Z.-Z. Chen ; X. He ; C.-H. Huang |
| Edge-Disjoint Routing in Plane Switch Graphs in Linear Time / K. Weihe |
| On Quantum and Classical Space-bounded Processes with Algebraic Transition Amplitudes |
| A Better Lower Bound for Quantum Algorithms Searching an Ordered List / A. Ambainis |
| Bounds for Small-Error and Zero-Error Quantum Algorithms / H. Buhrman ; R. Cleve ; R. de Wolf ; C. Zalka |
| Optimal Lower Bounds for Quantum Automata and Random Access Codes / A. Nayak |
| Improved Combinatorial Algorithms for the Facility Location and k-Median Problems / M. Charikar ; S. Guha |
| Lovasz's Lemma for the Three-Dimensional K-Level of Concave Surfaces and its Applications / N. Katoh ; T. Tokuyama |
| Cuts, Trees and l[subscript 1]-Embeddings of Graphs / A. Gupta ; I. Newman ; Y. Rabinovich |
| A Probabilistic Algorithm for k-SAT and Constraint Satisfaction Problems / U. Schoning |
| Random CNF's are Hard for the Polynomial Calculus / E. Ben-Sasson |
| A Study of Proof Search Algorithms for Resolution and Polynomial Calculus / M. L. Bonet ; N. Galesi |
| Online Scheduling to Minimize Average Stretch / S. Muthukrishnan ; R. Rajaraman ; A. Shaheen ; J. E. Gehrke |
| Weak Adversaries for the k-Server Problem / E. Koutsoupias |
| Finely-Competitive Paging / A. Blum ; C. Burch ; A. Kalai |
| On the Complexity of SAT / R. J. Lipton ; A. Viglas |
| Hardness of Approximating [characters not reproducible] Minimization Problems / C. Umans |
| Hardness of Approximating the Minimum Distance of a Linear Code / I. Dumer ; D. Micciancio ; M. Sudan |
| On Universal and Fault-Tolerant Quantum Computing: A Novel Basis and a New Constructive Proof of Universality for Shor's Basis / P. O. Boykin ; T. Mor ; M. Pulver ; V. Roychowdhury ; F. Vatan |
| Satisfiability of Word Equations with Constants is in PSPACE / W. Plandowski |
| An Approximate L[superscript 1]-Difference Algorithm for Massive Data Streams / J. Feigenbaum ; S. Kannan ; M. Strauss ; M. Viswanathan |
| Algorithmic Aspects of Protein Structure Similarity / D. Goldman ; S. Istrail ; C. H. Papadimitriou |
| Magic Functions / C. Dwork ; M. Naor ; L. Stockmeyer |
| Limits on the Efficiency of One-Way Permutation-Based Hash Functions / D. R. Simon |
| Non-Malleable Non-Interactive Zero Knowledge and Adaptive Chosen-Ciphertext Security / A. Sahai |
| Non-Interactive CryptoComputing For NC[superscript 1] / T. Sander ; A. Young ; M. Yung |
| Fairness in Routing and Load Balancing / Y. Rabani |
| Stochastic Load Balancing and Related Problems / A. Goel |
| Reducing Network Congestion and Blocking Probability Through Balanced Allocation / M. J. Luczak ; E. Upfal |
| Finding Maximal Repetitions in a Word in Linear Time / R. Kolpakov ; G. Kucherov |
| All Pairs Shortest Paths in Undirected Graphs with Integer Weights / A. Shoshan ; U. Zwick |
| An Algorithmic Theory of Learning: Robust Concepts and Random Projection / R. I. Arriaga ; S. Vempala |
| Boosting and Hard-Core Sets / A. R. Klivans ; R. A. Servedio |
| Learning Mixtures of Gaussians / S. Dasgupta |
| Regular Languages Are Testable with a Constant Number of Queries / N. Alon ; M. Krivelevich ; M. Szegedy |
| Efficient Testing of Large Graphs / E. Fischer |
| Author Index |
| Foreword |
| Committees |
| Machtey Award |
| Reviewers |
| Primal-Dual Approximation Algorithms for Metric Facility Location and k-Median Problems / K. Jain ; V. V. Vazirani |
| Approximation Algorithms for Classification Problems with Pairwise Relationships: Metric Labeling and Markov Random Fields / J. Kleinberg ; E. Tardos |
