33. STOC 2001: Heraklion, Crete, Greece

Proceedings on 33rd Annual ACM Symposium on Theory of Computing, July 6-8, 2001, Heraklion, Crete, Greece. ACM, 2001

Session 1A

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

Session 1B

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

Session 2A

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

Session 2B

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

Session 3A

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

Session 3B

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

Session 4A

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

Session 4B

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

Session 5A

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

Session 5B

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

Session 6A

Kamal Jain, Vijay V. Vazirani:
Applications of approximation algorithms to cooperative games. 364-372
Electronic Edition (ACM DL) BibTeX
Anna Moss, Yuval Rabani:
Approximation algorithms for constrained for constrained node weighted steiner tree problems. 373-382
Electronic Edition (ACM DL) BibTeX
Sudipto Guha, Adam Meyerson, Kamesh Munagala:
A constant factor approximation for the single sink edge installation problems. 383-388
Electronic Edition (ACM DL) BibTeX
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
Electronic Edition (ACM DL) BibTeX

Session 6B

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

Session 7A

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

Session 7B

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

Session 8A

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

Session 8B

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

Turing Award Lecture

Andrew Chi-Chih Yao:
Some perspective on computational complexity (abstract). 600
Electronic Edition (ACM DL) BibTeX

Session 10A

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

Session 10B

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

Session 11A

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

Session 11B

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

Session 12: Invited Pleanry Talks

Christos H. Papadimitriou:
Algorithms, games, and the internet. 749-753
Electronic Edition (ACM DL) BibTeX
Boris A. Trakhtenbrot:
Automata, circuits and hybrids: facets of continuous time. 754-755
Electronic Edition (ACM DL) BibTeX