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 |