default search action
Google
Google Scholar
Semantic Scholar
Internet Archive Scholar
CiteSeerX
ORCID33rd STOC 2001: Heraklion, Crete, Greece
- Jeffrey Scott Vitter, Paul G. Spirakis, Mihalis Yannakakis:
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 E. Shparlinski:
Sparse polynomial approximation in finite fields. 209-215 - Adam R. 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 R. 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 G. 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(2n/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 S. Vempala:
Optimal outlier removal in high-dimensional. 627-636 - Li-San Wang, Tandy J. 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
manage site settings
To protect your privacy, all features that rely on external API calls from your browser are turned off by default. You need to opt-in for them to become active. All settings here will be stored as cookies with your web browser. For more information see our F.A.Q.
last updated on 2025-11-16 23:49 CET by the dblp team
all metadata released as open data under CC0 1.0 license
see also: Terms of Use | Privacy Policy | Imprint
dblp was originally created in 1993 at:
since 2018, dblp has been operated and maintained by:
the dblp computer science bibliography is funded and supported by:
