Thirty-Third Annual ACM Symposium on Theory of Computing Crete, Greece July 6-8, 2001 THURSDAY JULY 5 19:00-21:00 Welcome Reception -------------------- FRIDAY JULY 6 8:30-10:10 SESSION 1A CHAIR Mihalis Yannakakis 8:30 Clustering to Minimize the Sum of Cluster Diameters Moses Charikar and Rina Panigrahy 8:55 Approximating Min-Sum k-Clustering in Metric Spaces Yair Bartal, Moses Charikar, and Danny Raz 9:20 Local Search Heuristics for k-median and Facility Location Problems Vijay Arya, Naveen Garg, Rohit Khandekar, Karnesh Munagala, Adam Mayerson, and Vinayaka Pandit 9:45 Profit-Earning Facility Location Adam Meyerson SESSION 1B CHAIR Noam Nisan 8:30 One-dimensional Quantum Walks Andris Ambainis, Eric Bach, Ashwin Nayak, Ashvin Vishwanath, and John Watrous 8:55 Quantum Walks on Graphs Dorit Aharonov, Andris Ambainis, Julia Kempe and Umesh Vazirani 9:20 Quantum Algorithms for Solvable Groups John Watrous 9:45 Quantum Mechanical Algorithms for the Nonabelian Hidden Subgroup Problem Michelangelo Grigni, Leonard Schulman, Monica Vazirani, and Umesh Vazirani 10:10-10:30 BREAK 10:30-12:10 SESSION 2A CHAIR Paul Spirakis 10:30 Minimax Parametric Optimization Problems and Multidimensional Parametric Searching Takeshi Tokuyama 10:55 Algorithms for Minimizing Weighted Flow Time Chandra Chekuri, Sanjeev Khanna, and An Zhu 11:20 Non-Clairvoyant Scheduling to Minimize the Average Flow Time on Single and Parallel Machines Luca Becchetti and Stefano Leonardi 11:45 Stackelberg Scheduling Strategies Tim Roughgarden SESSION 2B CHAIR Noam Nisan 10:30 Quantum Computers that Can be Simulated Classically in Polynomial Time Leslie G. Valiant 10:55 Interaction in Quantum Communication and the Complexity of Set Disjointness Hartmut Klauck, Ashwin Nayak, Amnon Ta-Shma, and David Zuckerman 11:20 A New Protocol and Lower Bounds for Quantum Coin Flipping Andris Ambainis 11:45 Loss-less Condensers, Unbalanced Expanders, and Extractors Amnon Ta-Shma, Christopher Umans, and David Zuckerman 12:10-2:00 LUNCH 2:00-3:40 SESSION 3A CHAIR Elias Koutsoupias 2:00 Conditions on Input Vectors for Consensus Solvability in Asynchronous Distributed Systems Achour Mostefaoui, Sergio Rajsbaum, and Michel Raynal 2:25 Spatial Gossip and Resource Location Protocols David Kempe, Jon Kleinberg, and Alan Demers 2:50 (1+epsilon,beta)-Spanner Constructions for General Graphs Michael Elkin and David Peleg 3:15 Approximate Distance Oracles Mikkel Thorup and Uri Zwick SESSION 3B CHAIR Russel Impagliazzo 2:00 Extractor Codes Amnon Ta-Shma and David Zuckerman 2:25 Excellent Nonlinear Codes from Modular Curves Noam D. Elkies 2:50 Sparse Polynomial Approximation in Finite Fields Igor Shparlinski 3:15 Randomness Efficient Identity Testing of Multivariate Polynomials Adam R. Klivans and Daniel A. Spielman 3:40-4:00 BREAK 4:00-6:05 SESSION 4A CHAIR Elias Koutsoupias 4:00 Fully-Dynamic Min-Cut Mikkel Thorup 4:25 Computing Crossing Numbers in Quadratic Time Martin Grohe 4:50 Dual Euler Paths in Series Parallel Graphs S. Rao Kosaraju 5:15 Decidability of String Graphs Marcus Schaefer and Daniel Stefankovic SESSION 4B CHAIR Sampath Kannan 4:00 Learning Mixtures of Arbitrary Gaussians Sanjeev Arora and Ravi Kannan 4:25 Learning DNF in Time $2^{\tilde{O}(n^{1/3})}$ Adam R. Klivans and Rocco A. Servedio 4:50 Sampling Algorithms: Lower Bounds and Applications Ziv Bar-Yossef, Ravi Kumar, and D. Sivakumar 5:15 Testing Metric Properties Michal Parnas and Dana Ron 5:40 Testing of Matrix Properties Eldar Fischer and Ilan Newman 9:00 Business Meeting ------------------------------ SATURDAY JULY 7 8:30-10:10 SESSION 5A CHAIR Kurt Melhorn 8:30 The Simplex Algorithm Usually Takes a Polynomial Number of Steps Daniel A. Spielman and Shang-Hua Teng 8:55 One Line and n Points Bernd Gaertner, Jozsef Solymosi, Falk Tschirschnitz, Pavel Valtr, and Emo Welzl 9:20 A Tight Bound for the Complexity of Voronoi Diagrams under Polyhedral Convex Distance Functions in 3D Christian Icking and Lihong Ma 9:45 Lower Bounds for Intersection Searching and Fractional Cascading in Higher Dimension Bernard Chazelle and Ding Liu SESSION 5B CHAIR Ronald Fagin 8:30 Sharp Threshold and Scaling Window for the Integer Partitioning Problem Christian Borgs, Jennifer T. Chayes, and Boris Pittel 8:55 A Sharp Threshold in Proof Complexity Dimitris Achlioptas, Paul Beame, and Michael Molloy 9:20 Regular Resolution Lower Bounds for the Weak Pigeonhole Principle Toniann Pitassi and Ran Raz 9:45 The Complexity of Analytic Tableaux Noriko H. Arai, Toniann Pitassi, and Alasdair Urquhart 10:10-10:30 BREAK 10:30-12:10 SESSION 6A CHAIR Kurt Melhorn 10:30 Applications of Approximation Algorithms to Cooperative Games Kamal Jain and Vijay V. Vazirani 10:55 Approximation Algorithms for Constrained Node Weighted Steiner Tree Problems Anna Moss and Yuval Rabani 11:20 A Constant Factor Approximation for the Single Sink Edge Installation Problem Sudipto Guha, Adam Meyerson, and Kamesh Munagala 11:45 Provisioning a Virtual Private Network: A Network Design Problem for Multicommodity Flow Anupam Gupta, Jon Kleinberg, Amit Kumar, Rajeev Rastogi, and Bulent Yener SESSION 6B CHAIR Ronald Fagin 10:30 Explicit Lower Bound of $4.5n-o(n)$ for Boolean Circuits Oded Lachish and Ran Raz 10:55 Lower Bounds for Matrix Product, in Bounded Depth Circuits With Arbitrary Gates Amir Shpilka and Ran Raz 11:20 A Read-Once Branching Program Lower Bound of Omega (2 exp (n/4)) for Integer Multiplication Using Universal Hashing Beate Bollig and Philipp Woelfel 11:45 On the Cell Probe Complexity of Membership and Perfect Hashing Rasmus Pagh 12:10-2:00 LUNCH 2:00-3:40 SESSION 7A CHAIR Chandra Chekuri 2:00 On the Integrality Ratio of Semidefinite Relaxations of MAX CUT Uriel Feige and Gideon Schechtman 2:25 Approximation Algorithms for MAX3CUT and Other Problems via Complex Semidefinite Programming Michel X. Goemans and David P. Williamson 2:50 Non-approximability Results for Optimization Problems on Bounded Degree Instances Luca Trevisan 3:15 Colouring Graphs when the Number of Colours is Nearly the Maximum Degree Michael Molloy and Bruce Reed SESSION 7B CHAIR S. Muthukrishnan 2:00 Data-Streams and Histograms Sudipto Guha, Nick Koudas, and Kyuseok Shim 2:25 Optimal Static Range Reporting in One Dimension Stephen Alstrup, Gerth S. Brodal, and Theis Rauhe 2:50 Biased Dictionaries with Fast Insert/Deletes Funda Ergun, S. Cenk Sahinalp, Jonathan Sharp, and Rakesh K. Sinha 3:15 Anti-persistence: History Independent Data Structures Moni Naor and Vanessa Teague 3:40-4:00 BREAK 4:00-6:05 SESSION 8A CHAIR Christos Papadimitriou 4:00 Dynamic TCP Acknowledgement and Other Stories About e/(e-1) Anna Karlin, Claire Kenyon, and Dana Randall 4:25 The Price of Selfish Routing Marios Mavronicolas and Paul Spirakis 4:50 Buffer Overflow Management in QoS Switches Alexander Kesselman, Zvi Lotker, Yishay Mansour, Boaz Patt-Shamir, Baruch Schieber, and Maxim Sviridenko 5:15 Almost Optimal Permutation Routing on Hypercubes Berthold V"ocking 5:40 Online Server Allocation in a Server Farm via Benefit Task Systems T.S. Jayram, Tracy J. Kimbrel, Robert Krauthgamer, Baruch Schieber, and Maxim Sviridenko SESSION 8B CHAIR Joan Feigenbaum 4:00 Private Approximation of NP-hard Functions Shai Halevi, Robert Krauthgamer, Eyal Kushilevitz, and Kobbi Nissim 4:25 Concurrent and Resettable Zero-Knowledge in Poly-logarithmic Rounds Joe Kilian and Erez Petrank 4:50 Black-Box Concurrent Zero-Knowledge Requires $\tilde{\Omega}(\log n)$ Rounds Ran Canetti, Joe Kilian, Erez Petrank, and Alon Rosen 5:15 The Round Complexity of Verifiable Secret Sharing and Secure Multicast Rosario Gennaro, Yuval Ishai, Eyal Kushilevitz, and Tal Rabin 5:40 Communication Preserving Protocols for Secure Function Evaluation Moni Naor and Kobbi Nissim ---------------- SUNDAY JULY 8 8:30-9:30 SESSION 9: Invited Plenary Talk CHAIR Mihalis Yannakakis Turing Award Lecture: Some Perspectives on Computational Complexity Andrew C. C. Yao 9:30 - 9:50 BREAK 9:50-11:55 SESSION 10A CHAIR Prabhakar Raghavan 9:50 A Sieve Algorithm for the Shortest Lattice Vector Problem Miklos Ajtai, Ravi Kumar, and D. Sivakumar 10:15 Fast Computation of Low Rank Matrix Approximations Dimitris Achlioptas and Frank McSherry 10:40 Spectral Analysis of Data Yossi Azar, Amos Fiat, Anna Karlin, Frank McSherry, and Jared Saia 11:05Near-Optimal Outlier Removal in High-Dimensional Spaces John Dunagan and Santosh Vempala 11:30 New Polynomial Time Methods for Whole Genome Phylogeny Reconstruction Li-San Wang and Tandy Warnow SESSION 10B CHAIR Sampath Kannan 9:50 On Optimal Slicing of Parallel Programs Markus Mueller-Olm and Helmut Seidl 10:15 When is the Evaluation of Conjunctive Queries Tractable ? Martin Grohe, Thomas Schwentick, and Luc Segoufin 10:40 The Complexity of Maximal Constraint Languages Andrei A. Bulatov, Andrei A. Krokhin, and Peter G. Jeavons 11:05 Quantitative Solution of Omega-Regular Games Luca de Alfaro and Rupak Majumdar 11:30 Distribution Functions of Probabilistic Automata Farrokh Vatan 11:55-1:45 LUNCH 1:45-3:00 SESSION 11A CHAIR Prabhakar Raghavan 1:45 Compatible Sequences and a Slow Winkler Percolation Peter Gacs 2:10 Edge Isoperimetry and Rapid Mixing on Matroids and Geometric Markov Chains Ravi Montenegro and Jun-Bae Son 2:35 A polynomial-time approximation algorithm for the permanent of a matrix with non-negative entries Mark Jerrum, Alistair Sinclair, and Eric Vigoda SESSION 11B CHAIR S. Muthukrishnan 1:45 Computing with Continuous-time Liapunov Systems Jiri Sima and Pekka Orponen 2:10 Complex Tilings Bruno Durand, Leonid Levin, and Alexander Shen 2:35 Running Time and Program Size for Self-assembled Squares Leonard Adleman, Qi Cheng, Ashish Goel, and Ming-Deh Huang 3:00-3:20 BREAK 3:20-6:20 SESSION 12: Invited Plenary Talks (Joint STOC-ICALP Session) CHAIR Paul Spirakis 3:20 Greek Computer Society - Computer Technology Institute Award Lecture: Algorithms, Games, and the Internet Christos H. Papadimitriou 4:20 80th Birthday Celebration Lecture: Automata and Circuits: Facets of Continuous Time Boris Trakhtenbrot 5:20 Goedel Award Lecture: Reflections on the PCP theorem and its consequences Uriel Feige 8:00 Greetings from major sponsors from the Greek Industry and Representatives of the Greek Government and the Commission of the European Union 9:00 JOINT BANQUET STOC - ICALP