• 
  Jeffrey Scott Vitter, Paul G. Spirakis, Mihalis Yannakakis (Eds.): Proceedings on 33rd Annual ACM Symposium on Theory of Computing, July 6-8, 2001, Heraklion, Crete, Greece. ACM 2001 ISBN 1-58113-349-9

Session 1A

• 
  Moses Charikar, Rina Panigrahy: Clustering to minimize the sum of cluster diameters. 1-10
• 
  Yair Bartal, Moses Charikar, Danny Raz: Approximating min-sum k-clustering in metric spaces. 11-20
• 
  Vijay Arya, Naveen Garg, Rohit Khandekar, Adam Meyerson, Kamesh Munagala, Vinayaka Pandit: Local search heuristic for k-median and facility location problems. 21-29
• 
  Adam Meyerson: Profit-earning facility location. 30-36

Session 1B

• 
  Andris Ambainis, Eric Bach, Ashwin Nayak, Ashvin Vishwanath, John Watrous: One-dimensional quantum walks. 37-49
• 
  Dorit Aharonov, Andris Ambainis, Julia Kempe, Umesh V. Vazirani: Quantum walks on graphs. 50-59
• 
  John Watrous: Quantum algorithms for solvable groups. 60-67
• 
  Michelangelo Grigni, Leonard J. Schulman, Monica Vazirani, Umesh V. Vazirani: Quantum mechanical algorithms for the nonabelian hidden subgroup problem. 68-74

Session 2A

• 
  Takeshi Tokuyama: Minimax parametric optimization problems and multi-dimensional parametric searching. 75-83
• 
  Chandra Chekuri, Sanjeev Khanna, An Zhu: Algorithms for minimizing weighted flow time. 84-93
• 
  Luca Becchetti, Stefano Leonardi: Non-clairvoyant scheduling to minimize the average flow time on single and parallel machines. 94-103
• 
  Tim Roughgarden: Stackelberg scheduling strategies. 104-113

Session 2B

• 
  Leslie G. Valiant: Quantum computers that can be simulated classically in polynomial time. 114-123
• 
  Hartmut Klauck, Ashwin Nayak, Amnon Ta-Shma, David Zuckerman: Interaction in quantum communication and the complexity of set disjointness. 124-133
• 
  Andris Ambainis: A new protocol and lower bounds for quantum coin flipping. 134-142
• 
  Amnon Ta-Shma, Christopher Umans, David Zuckerman: Loss-less condensers, unbalanced expanders, and extractors. 143-152

Session 3A

• 
  Achour Mostéfaoui, Sergio Rajsbaum, Michel Raynal: Conditions on input vectors for consensus solvability in asynchronous distributed systems. 153-162
• 
  David Kempe, Jon M. Kleinberg, Alan J. Demers: Spatial gossip and resource location protocols. 163-172
• 
  Michael Elkin, David Peleg: (1+epsilon, beta)-spanner constructions for general graphs. 173-182
• 
  Mikkel Thorup, Uri Zwick: Approximate distance oracles. 183-192

Session 3B

• 
  Amnon Ta-Shma, David Zuckerman: Extractor codes. 193-199
• 
  Noam D. Elkies: Excellent codes from modular curves. 200-208
• 
  Igor Shparlinski: Sparse polynomial approximation in finite fields. 209-215
• 
  Adam Klivans, Daniel A. Spielman: Randomness efficient identity testing of multivariate polynomials. 216-223

Session 4A

• 
  Mikkel Thorup: Fully-dynamic min-cut. 224-230
• 
  Martin Grohe: Computing crossing numbers in quadratic time. 231-236
• 
  S. Rao Kosaraju: Euler paths in series parallel graphs. 237-240
• 
  Marcus Schaefer, Daniel Stefankovic: Decidability of string graphs. 241-246

Session 4B

• 
  Sanjeev Arora, Ravi Kannan: Learning mixtures of arbitrary gaussians. 247-257
• 
  Adam Klivans, Rocco A. Servedio: Learning DNF in time 2^Õ(n1/3). 258-265
• 
  Ziv Bar-Yossef, Ravi Kumar, D. Sivakumar: Sampling algorithms: lower bounds and applications. 266-275
• 
  Michal Parnas, Dana Ron: Testing metric properties. 276-285
• 
  Eldar Fischer, Ilan Newman: Testing of matrix properties. 286-295

Session 5A

• 
  Daniel A. Spielman, Shang-Hua Teng: Smoothed analysis of algorithms: why the simplex algorithm usually takes polynomial time. 296-305
• 
  Bernd Gärtner, József Solymosi, Falk Tschirschnitz, Emo Welzl, Pavel Valtr: One line and n points. 306-315
• 
  Christian Icking, Lihong Ma: A tight bound for the complexity of voroni diagrams under polyhedral convex distance functions in 3D. 316-321
• 
  Bernard Chazelle, Ding Liu: Lower bounds for intersection searching and fractional cascading in higher dimension. 322-329

Session 5B

• 
  Christian Borgs, Jennifer T. Chayes, Boris Pittel: Sharp threshold and scaling window for the integer partitioning problem. 330-336
• 
  Dimitris Achlioptas, Paul Beame, Michael S. O. Molloy: A sharp threshold in proof complexity. 337-346
• 
  Toniann Pitassi, Ran Raz: Regular resolution lower bounds for the weak pigeonhole principle. 347-355
• 
  Noriko H. Arai, Toniann Pitassi, Alasdair Urquhart: The complexity of analytic tableaux. 356-363

Session 6A

• 
  Kamal Jain, Vijay V. Vazirani: Applications of approximation algorithms to cooperative games. 364-372
• 
  Anna Moss, Yuval Rabani: Approximation algorithms for constrained for constrained node weighted steiner tree problems. 373-382
• 
  Sudipto Guha, Adam Meyerson, Kamesh Munagala: A constant factor approximation for the single sink edge installation problems. 383-388
• 
  Anupam Gupta, Jon M. Kleinberg, Amit Kumar, Rajeev Rastogi, Bülent Yener: Provisioning a virtual private network: a network design problem for multicommodity flow. 389-398

Session 6B

• 
  Oded Lachish, Ran Raz: Explicit lower bound of 4.5n - o(n) for boolena circuits. 399-408
• 
  Ran Raz, Amir Shpilka: Lower bounds for matrix product, in bounded depth circuits with arbitrary gates. 409-418
• 
  Beate Bollig, Philipp Woelfel: A read-once branching program lower bound of Omega(2^n/4) for integer multiplication using universal. 419-424
• 
  Rasmus Pagh: On the cell probe complexity of membership and perfect hashing. 425-432

Session 7A

• 
  Uriel Feige, Gideon Schechtman: On the integrality ratio of semidefinite relaxations of MAX CUT. 433-442
• 
  Michel X. Goemans, David P. Williamson: Approximation algorithms for MAX-3-CUT and other problems via complex semidefinite programming. 443-452
• 
  Luca Trevisan: Non-approximability results for optimization problems on bounded degree instances. 453-461
• 
  Michael Molloy, Bruce A. Reed: Colouring graphs when the number of colours is nearly the maximum degree. 462-470

Session 7B

• 
  Sudipto Guha, Nick Koudas, Kyuseok Shim: Data-streams and histograms. 471-475
• 
  Stephen Alstrup, Gerth Stølting Brodal, Theis Rauhe: Optimal static range reporting in one dimension. 476-482
• 
  Funda Ergün, Süleyman Cenk Sahinalp, Jonathan Sharp, Rakesh K. Sinha: Biased dictionaries with fast insert/deletes. 483-491
• 
  Moni Naor, Vanessa Teague: Anti-presistence: history independent data structures. 492-501

Session 8A

• 
  Anna R. Karlin, Claire Kenyon, Dana Randall: Dynamic TCP acknowledgement and other stories about e/(e-1). 502-509
• 
  Marios Mavronicolas, Paul G. Spirakis: The price of selfish routing. 510-519
• 
  Alexander Kesselman, Zvi Lotker, Yishay Mansour, Boaz Patt-Shamir, Baruch Schieber, Maxim Sviridenko: Buffer overflow management in QoS switches. 520-529
• 
  Berthold Vöcking: Almost optimal permutation routing on hypercubes. 530-539
• 
  T. S. Jayram, Tracy Kimbrel, Robert Krauthgamer, Baruch Schieber, Maxim Sviridenko: Online server allocation in a server farm via benefit task systems. 540-549

Session 8B

• 
  Shai Halevi, Robert Krauthgamer, Eyal Kushilevitz, Kobbi Nissim: Private approximation of NP-hard functions. 550-559
• 
  Joe Kilian, Erez Petrank: Concurrent and resettable zero-knowledge in poly-loalgorithm rounds. 560-569
• 
  Ran Canetti, Joe Kilian, Erez Petrank, Alon Rosen: Black-box concurrent zero-knowledge requires Omega~(log n) rounds. 570-579
• 
  Rosario Gennaro, Yuval Ishai, Eyal Kushilevitz, Tal Rabin: The round complexity of verifiable secret sharing and secure multicast. 580-589
• 
  Moni Naor, Kobbi Nissim: Communication preserving protocols for secure function evaluation. 590-599

Turing Award Lecture

• 
  Andrew Chi-Chih Yao: Some perspective on computational complexity (abstract). 600

Session 10A

• 
  Miklós Ajtai, Ravi Kumar, D. Sivakumar: A sieve algorithm for the shortest lattice vector problem. 601-610
• 
  Dimitris Achlioptas, Frank McSherry: Fast computation of low rank matrix. 611-618
• 
  Yossi Azar, Amos Fiat, Anna R. Karlin, Frank McSherry, Jared Saia: Spectral analysis of data. 619-626
• 
  John Dunagan, Santosh Vempala: Optimal outlier removal in high-dimensional. 627-636
• 
  Li-San Wang, Tandy Warnow: Estimating true evolutionary distances between genomes. 637-646

Session 10B

• 
  Markus Müller-Olm, Helmut Seidl: On optimal slicing of parallel programs. 647-656
• 
  Martin Grohe, Thomas Schwentick, Luc Segoufin: When is the evaluation of conjunctive queries tractable? 657-666
• 
  Andrei A. Bulatov, Andrei A. Krokhin, Peter Jeavons: The complexity of maximal constraint languages. 667-674
• 
  Luca de Alfaro, Rupak Majumdar: Quantitative solution of omega-regular games. 675-683
• 
  Farrokh Vatan: Distribution functions of probabilistic automata. 684-693

Session 11A

• 
  Péter Gács: Compatible sequences and a slow Winkler percolation. 694-703
• 
  Ravi Montenegro, Jung-Bae Son: Edge isoperimetry and rapid mixing on matroids and geometric Markov chains. 704-711
• 
  Mark Jerrum, Alistair Sinclair, Eric Vigoda: A polynomial-time approximation algorithm for the permanent of a matrix with non-negative entries. 712-721

Session 11B

• 
  Jirí Síma, Pekka Orponen: Computing with continuous-time Liapunov systems. 722-731
• 
  Bruno Durand, Leonid A. Levin, Alexander Shen: Complex tilings. 732-739
• 
  Leonard M. Adleman, Qi Cheng, Ashish Goel, Ming-Deh A. Huang: Running time and program size for self-assembled squares. 740-748

Session 12: Invited Pleanary Talks

• 
  Christos H. Papadimitriou: Algorithms, games, and the internet. 749-753
• 
  Boris A. Trakhtenbrot: Automata, circuits and hybrids: facets of continuous time. 754-755