33. STOC 2001: Heraklion, Crete, Greece

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 Pleanry Talks

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