| Foreword |
| Committees |
| Reviewers |
| Geometric Computation and the Art of Sampling / Emo Welzl ; J. MatousekTutorial I： |
| Theoretical Issues in Probabilistic Artificial Intelligence / Sally Goldman ; M. KearnsTutorial II： |
| Information Retrieval on the Web / David Karger ; A. Broder ; M.R. HenzingerTutorial III： |
| A Tight Characterization of NP with 3 Query PCPs / Mihir Bellare ; V. Guruswami ; D. Lewin ; M. Sudan ; L. TrevisanSession 1A： |
| Probabilistically Checkable Proofs with Low Amortized Query Complexity |
| Improved Decoding of Reed-Solomon and Algebraic-Geometric Codes |
| The Access Network Design Problem / Jon Kleinberg ; M. Andrews ; L. ZhangSession 1B： |
| Jitter Control in QoS Networks / Y. Mansour ; B. Patt-Shamir |
| Stability of Adversarial Queues via Fluid Models / D. Gamarnik |
| Delayed Information and Action in On-line Algorithms / S. Albers ; M. Charikar ; M. Mitzenmacher |
| The Complexity of the Approximation of the Bandwidth Problem / Miklos Ajtai ; W. UngerSession 2A： |
| The Shortest Vector in a Lattice is Hard to Approximate to Within Some Constant / D. Micciancio |
| Approximating-CVP to Within Almost-Polynomial Factors is NP-Hard / I. Dinur ; G. Kindler ; S. Safra |
| Satisfiability of Word Equations with Constants is in Exponential Space / Christos Papadimitriou ; C. GutierrezSession 2B： |
| Decidability of Bisimulation Equivalence for Equational Graphs of Finite Out-Degree / G. Senizergues |
| A Primitive Recursive Algorithm for the General Petri Net Reachability Problem / Z. Bouziane |
| Algorithms to Tile the Infinite Grid with Finite Clusters / M. Szegedy |
| On Approximate Nearest Neighbors in Non-Euclidean Spaces / Frances Yao ; P. IndykSession 3A： |
| Pattern Matching for Spatial Point Sets / D.E. Cardoze ; L.J. Schulman |
| Faster Algorithms for String Matching Problems: Matching the Convolution Bound |
| Overcoming the Memory Bottleneck in Suffix Tree Construction / M. Farach ; P. Ferragina ; S. Muthukrishnan |
| Bivariate Polynomial Multiplication / Dan Spielman ; M. BlaserSession 3B： |
| A Unified Superfast Algorithm for Boundary Rational Tangential Interpolation Problems and for Inversion and Factorization of Dense Structured Matrices / V. Olshevsky ; V. Pan |
| Unsatisfiable Systems of Equations, Over a Finite Field / A.R. Woods |
| Multiplicative Complexity of Taylor Shifts and a New Twist of the Substitution Method / A. Schonhage |
| Local Search in Smooth Convex Sets / David Williamson ; R. Kannan ; A. NolteSession 4A： |
| A TDI System and its Application to Approximation Algorithms / M.-c. Cai ; X. Deng ; W. Zang |
| Geometric Separator Theorems and Applications / W.D. Smith ; N.C. Wormald |
| Approximation of Diameters: Randomization Doesn't Help / A. Brieden ; P. Gritzmann ; V. Klee ; L. Lovasz ; M. Simonovits |
| Time-Space Tradeoffs for Branching Programs / Allan Borodin ; P. Beame ; M. Saks ; J.S. ThathacharSession 4B： |
| Optimal Time-Space Trade-Offs for Sorting / J. Pagter ; T. Rauhe |
| Exponential Complexity Lower Bounds for Depth 3 Arithmetic Circuits in Algebras of Functions Over Finite Fields / D. Grigoriev ; A.A. Razborov |
| Lower Bounds for (MOD p-MOD m) Circuits / V. Grolmusz ; G. Tardos |
| On the Single-Source Unsplittable Flow Problem / Y. Dinitz ; N. Garg ; M.X. GoemansSession 5A： |
| Faster and Simpler Algorithms for Multicommodity Flow and Other Fractional Packing Problems / J. Konemann |
| All Pairs Shortest Paths in Weighted Directed Graphs--Exact and Almost Exact Algorithms / U. Zwick |
| A Divide-and-Conquer Algorithm for Min-Cost Perfect Matching in the Plane / K.R. Varadarajan |
| 1-Way Quantum Finite Automata: Strengths, Weaknesses and Generalizations / Edith Cohen ; A. Ambainis ; R. FreivaldsSession 5B： |
| The Quantum Communication Complexity of Sampling / A. Ta-Shma ; U. Vazirani ; A. Wigderson |
| Quantum Lower Bounds by Polynomials / R. Beals ; H. Buhrman ; R. Cleve ; M. Mosca ; R. de Wolf |
| Quantum Oracle Interrogation: Getting All Information for Almost Half the Price / W. van Dam |
| Fast Monte-Carlo Algorithms for Finding Low-Rank Approximations / A. Frieze ; S. VempalaSession 6A： |
| Approximating a Finite Metric by a Small Number of Tree Metrics / C. Chekuri ; A. Goel ; S. Guha ; S Plotkin |
| Random Projection: A New Approach to VLSI Layout |
| Map Graphs in Polynomial Time / M. Thorup |
| On Learning Monotone Boolean Functions / A. Blum ; C. Burch ; J. LangfordSession 6B： |
| Orchestrating Quartets: Approximation and Data Correction / T. Jiang ; P. Kearney ; M. Li |
| Testing Monotonicity / O. Goldreich ; S. Goldwasser ; E. Lehman ; D. Ron |
| Evolutionary Trees can be Learned in Polynomial Time in the Two-State General Markov Model / M. Cryan ; L.A. Goldberg ; P.W. Goldberg |
| A Factor 2 Approximation Algorithm for the Generalized Steiner Network Problem / Joseph Naor ; K. JainSession 7A： |
| The Finite Capacity Dial-A-Ride Problem / B. Raghavachari |
| A Randomized Approximation Scheme for Metric MAX-CUT / W.F. de la Vega ; C. Kenyon |
| Semidefinite Relaxations for Parallel Machine Scheduling / M. Skutella |
| Lower Bounds for Zero Knowledge on the Internet / J. Kilian ; E. Petrank ; C. RackoffSession 7B： |
| Oblivious Transfer with a Memory-Bounded Receiver / C. Cachin ; C. Crepeau ; J. Marcil |
| Quantum Cryptography with Imperfect Apparatus / D. Mayers ; A. Yao |
| The Security of Individual RSA Bits / J. Hastad ; M. Naslund |
| Protocols for Asymmetric Communication Channels / M. Adler ; B.M. MaggsSession 8A： |
| Marked Ancestor Problems / S. Alstrup ; T. Husfeldt |
| Towards an Optimal Bit-Reversal Permutation Program / L. Carter ; K.S. Gatlin |
| The Minimum Equivalent DNF Problem and Shortest Implicants / C. UmansSession 8B： |
| Concurrent Reachability Games / L. de Alfaro ; T.A. Henzinger ; O. Kupferman |
| Perfect Information Leader Election in log* n + O (1) Rounds / A. Russell ; D. Zuckerman |
| Random Sampling, Halfspace Range Reporting, and Construction of ([less than or equal] k)-Levels in Three Dimensions / T.M. ChanSession 9A： |
| Parametric and Kinetic Minimum Spanning Trees / P.K. Agarwal ; D. Eppstein ; L.J. Guibas |
| On the Combinatorial and Topological Complexity of a Single Cell / S. Basu |
| Which Crossing Number is it, Anyway? / J. Pach ; G. Toth |
| An Improved Exponential-Time Algorithm for k-SAT / Toni Pitassi ; R. Paturi ; P. Pudlak ; M.E. Saks ; F. ZaneSession 9B： |
| Exponential Separations between Restricted Resolution and Cutting Planes Proof Systems / M.L. Bonet ; J.L. Esteban ; N. Galesi ; J. Johannsen |
| Tseitin's Tautologies and Lower Bounds for Nullstellensatz Proofs |
| Which Problems Have Strongly Exponential Complexity? / R. Impagliazzo |
| Recommendation Systems: A Probabilistic Analysis / R. Kumar ; P. Raghavan ; S. Rajagopalan ; A. TomkinsSession 10A： |
| Heuristics for Finding Large Independent Sets, with Applications to Coloring Semi-Random Graphs / U. Feige |
| Improved Bounds and Algorithms for Hypergraph Two-Coloring / J. Radhakrishnan ; A. Srinivasan |
| Local Divergence of Markov Chains and the Analysis of Iterative Load-Balancing Schemes / Y. Rabani ; A. Sinclair ; R. Wanka |
| The Complexity of Acyclic Conjunctive Queries / G. Gottlob ; N. Leone ; F. ScarcelloSession 10B： |
| A Characterization of NC by Tree Recurrence / D. Leivant |
| A Linguistic Characterization of Bounded Oracle Computation and Probabilistic Polynomial Time / J. Mitchell ; M. Mitchell ; A. Scedrov |
| Randomness vs. Time: De-Randomization under a Uniform Assumption |
| Author Index |
| Foreword |
| Committees |
| Reviewers |
| Geometric Computation and the Art of Sampling / Emo Welzl ; J. MatousekTutorial I： |
| Theoretical Issues in Probabilistic Artificial Intelligence / Sally Goldman ; M. KearnsTutorial II： |
| Information Retrieval on the Web / David Karger ; A. Broder ; M.R. HenzingerTutorial III： |
