Program of the Thirty-Second Annual ACM Symposium on Theory of Computing May 21-23, 2000, Portland, Oregon, USA Important Note: There will be a workshop on "Challenges for Theoretical Computer Science" on Saturday, May 20, the day before the STOC conference starts. Details will be posted on the SIGACT web page as they become available. Sunday, May 21, 2000 Session 1A Chair: Frances Yao 8:30 am Extractors and pseudo-random generators with optimal seed length Russell Impagliazzo, Ronen Shaltiel, and Avi Wigderson 8:55 am Pseudo-random functions and factoring Moni Naor, Omer Reingold, and Alon Rosen 9:20 am Satisfiability of equations in free groups is in PSPACE Claudio Gutierrez 9:45 am Setting 2 variables at a time yields a new lower bound for random 3-SAT Dimitris Achlioptas Sessions 1B Chair: Ding-Zhu Du 8:30 am A new algorithmic approach to the general Lovasz Local Lemma with applications to scheduling and satisfiability problems Artur Czumaj and Christian Scheideler 8:55 am A deterministic polynomial-time algorithm for approximating mixed discriminant and mixed volume Leonid Gurvits and Alex Samorodnitsky 9:20 am Randomized metarounding Robert Carr and Santosh Vempala 9:45 am Isomorphism testing for embeddable graphs through definability Martin Grohe Coffee Break 10:10 am - 10:30 am Session 2A Chair: Frances Yao 10:30 am Circuit minimization problem Valentine Kabanets and Jin-Yi Cai 10:55 am On the efficiency of local decoding procedures for error-correcting codes Jonathan Katz and Luca Trevisan 11:20 am Statistical mechanics, three-dimensionality and NP-completeness Sorin Istrail Session 2B Chair: Ding-Zhu Du 10:30 am A combinatorial, strongly polynomial-time algorithm for minimizing submodular functions Santoru Iwata and Lisa Fleischer and Santoru Fujishige 10:55 am Improved algorithms for submodular function minimization and submodular flow Lisa Fleischer and Satoru Iwata 11:20 am On dual minimum cost flow algorithms Jens Vygen Lunch 11:50 am 1:20 pm Invited Session: Some Problems Related to Content Distribution Tom Leighton, Department of Mathematics, MIT, and Akamai Technologies Session 3A Chair: Steven Rudich 2:20 pm On the approximability of the traveling salesman problem Christos H Papadimitriou and Santosh Vempala 2:45pm Approximating the domatic number Uriel Feige, Magnus M Halldorsson, and Guy Kortsarz 3:10 pm The value of strong inapproximability results for clique Aravind Srinivasan Sessions 3B Chair: Eva Tardos 2:20 pm Compression using efficient multicasting Micah Adler and Tom Leighton 2:45 pm The small-world phenomenon: an algorithmic perspective Jon Kleinberg 3:10 pm A random graph model for massive graphs William Aiello, Fan Chung, and Linyuan Lu Coffee Break 3:35 - 3:55 pm Session 4A Chair: Steven Rudich 3:55 pm List decoding algorithms for certain concatenated codes Venkatesan Guruswami and Madhu Sudan 4:20 pm A PCP characterization of NP with optimal amortized query complexity Alex Samorodnitsky and Luca Trevisan 4:45 pm On transformations of interactive proofs that preserve the prover's complexity Salil Vadhan Sessions 4B Chair: Eva Tardos 3:55 pm On the sum-of-squares algorithm for bin packing Janos Csirik, David S Johnson, Claire Kenyon, James B Orlin, Peter W Shor, and Richard R Weber 4:20 pm Sharing the cost of multicast transmissions Joan Feigenbaum, Christos Papadimitriou, and Scott Shenker 4:45 pm The risk profile problem for stock portfolio optimization Ming-Yang Kao and Andreas Nolte and Stephen R Tate Monday, May 22, 2000 Session 5A Chair: Rafail Ostrovsky 8:30 am Resettable zero-knowledge Ran Canetti, Oded Goldreich, Sha, Goldwasser and Silvio Micali 8:55 am Complete characterization of security notions for probabilistic private-key encryption Jonathan Katz and Moti Yung 9:20 am On zero-knowledge proofs: "from membership to decision" Giovanni Di Crescenzo, Kouichi Sakurai, and Moti Yung 9:45 am Finding smooth integers in short intervals using CRT decoding Dan Boneh Sessions 5B Chair: David Eppstein 8:30 am Smoothing and cleaning up slivers Herbert Edelsbrunner, Xiang-Yang Li, Garry Miller, Andreas Stathopoulos, Dafna Talmor, Shang-Hua Teng, Alper Ungor, and Noel Walkington 8:55 am Hard-potato routing Costas Busch, Maurice Herlihy, and Roger Wattenhofer 9:20 am Approximation algorithms for geometric shortest path problems Lyudmil Aleksandrov, Anil Maheshwari, and Jorg-Rudiger Sack 9:45 am Improved approximations of crossings in graph drawings and VLSI layout areas Guy Even, Sudipto Guha, and Baruch Schieber Coffee Break 10:10 am - 10:30 am Sessions 6A Chair: Rafail Ostrovsky 10:30 am On the decidability of accessibility problems Rajeev Motwani, Rina Panigrahy, Vijay Saraswat, and Suresh Venkatasubramanian 10:55 am More general completeness theorems for secure two-party computation Joe Kilian 11:20 am On the complexity of verifiable secret sharing and multiparty computation Ronald Cramer, Ivan Damgard, and Stefan Dziembowski Session 6B: David Eppstein 10:30 am Tight(er) worst-case bounds on dynamic searching and priority queues Arne Andersson and Mikkel Thorup 10:55 am Near-optimal fully-dynamic graph connectivity Mikkel Thorup 11:20 am A new NC-algorithm for finding a perfect matching in bipartite planar and small genus graphs Meena Mahajan and Kasturi R Varadarajan Lunch 11:50 am Session 7A Chair: Sally Goldman 1:20 pm Space complexity in propositional calculus Michael Alekhnovich, Eli Ben-Sasson, Alexander A Razborov, and Avi Wigderson 1:45 pm A new proof of the weak pigeonhole principle Alexis Maciel, Toniann Pitassi, and Alan R Woods 2:10 pm Higher lower bounds on monotone size Danny Harnik and Ran Raz 2:35 pm Tighter lower bounds for nearest neighbor search and related problems in the cell probe model Omer Barkol and Yuval Rabani Sessions 7B Chair: Pavel Pevzner 1:20 pm Compressed suffix arrays and suffix trees with applications to text indexing and string matching Roberto Grossi and Jeffrey Scott Vitter 1:45 pm Faster suffix tree construction with missing suffix links Richard Cole and Ramesh Hariharan 2:10 pm Approximate nearest neighbors and sequence comparison with block operations S Muthukrishnan and Suleyman Cenk Sahinalp 2:35 pm Near optimal multiple alignment within a band in polynomial time Ming Li, Bin Ma, and Lusheng Wang Coffee Break 3:00 - 3:20 pm Sessions 8A Chair: Sally Goldman 3:20 pm Noise-tolerant learning, the parity problem, and the statistical query model Avrim Blum and Adam Kalai and Hal Wasserman 3:45 pm More theory revision with queries Judy Goldsmith and Robert H Sloan 4:10 pm Are bitvectors optimal? H Buhrman and PB Miltersen and J Radhakrishnan and S Venkatesh Sessions 8B Chair: Pavel Pevzner 3:20 pm The program-size complexity of self-assembled squares Paul W K Rothemund and Erik Winfree 3:45 pm Shortest path queries in planar graphs Danny Z Chen and Jinhui Xu 4:10 pm How tall is a tree? Bruce Reed Tuesday, May 23, 2000 Session 9A Chair: Eli Upfal 8:30 am Random walks with "back buttons" Ronald Fagin, Anna Karlin, Jon Kleinberg, Prabhakar Raghavan, Sridhar Rajagopalan, Ronitt Rubinfeld, Madhu Sudan, and Andrew Tomkins 8:55 am From partial consistency to global broadcast Matthias Fitzi and Ueli Maurer 9:20 am Connectivity and inference problems for temporal networks David Kempe, Jon Kleinberg, and Amit Kumar 9:45 am Strictly non-blocking WDM cross-connects for heterogeneous networks April Rasala and Gordon Wilfong Sessions 9B Chair: Sanjeev Khanna 8:30 am Finding long paths and cycles in sparse Hamiltonian graphs Tomas Feder, Rajeev Motwani, and Carlos Subi 8:55 am Approximating the minimum bisection size Uriel Feige, Robert Krauthgamer, and Kobbi Nissim 9:20 am A matter of degree: Improved approximation algorithms for degree-bounded minimum spanning trees J Konemann and R Ravi 9:45 am Clustering for edge-cost minimization Leonard J Schulman Coffee Break 10:10 am - 10:30 am Sessions 10A Chair: Eli Upfal 10:30 am Exact computation of the inertia of symmetric integer matrices Steven Fortune 10:55 am ffl-optimization schemes and L-bit precision: alternative perspectives in combinatorial optimization James B Orlin, Andreas S Schulz, and Sudipta Sengupta 11:20 am Matrix-vector product for confluent Cauchy-like matrices with application to confluent rational interpolation Vadim Olshevsky and Amin Shokrollahi Session 10B Chair: Sanjeev Khanna 10:30 am Query strategies for priced information Moses Charikar, Ron Fagin, Venkatesan Guruswami, Jon Kleinberg, Prabhakar Raghavan, and Amit Sahai 10:55 am A guessing game and randomized online algorithms Steven S Seiden 11:20 am Computing the median with uncertainty Tomas Feder, Rajeev Motwani, Rina Panigrahy, Chris Olston, and Jennifer Widom Lunch 11:50 am Session 11A Chair: Charles Bennett 1:20 pm Parallelization, amplification, and exponential time simulation of quantum interactive proof systems Alexei Kitaev and John Watrous 1:45 pm Rapid sampling through quantum computing Lov K Grover 2:10 pm Normal subgroup reconstruction and quantum computation using group representations Sean Hallgren, Alexander Russell, and Amnon Ta-Shma 2:35 pm Quantum lower bounds by quantum arguments Andris Ambainis 3:00 pm On quantum and probabilistic communication: Las Vegas and one-way protocols Hartmut Klauck Sessions 11B Chair: Andrei Broder 1:20 pm A constant factor approximation algorithm for a class of classification problems Anupam Gupta and Eva Tardos 1:45 pm Polynomial-time approximation scheme for data broadcast Claire Kenyon, Nicolas Schabanel, and Neal Young 2:10 pm Approximating permanents of complex matrices Martin Furer 2:35 pm Combining fairness with throughput: Online routing with multiple objectives Ashish Goel, Adam Meyerson, and Serge Plotkin 3:00 pm Improvements in throughput maximization for real-time scheduling Piotr Berman and Bhaskar DasGupta Coffee Break 3:25 - 3:40 pm Session 12A Chair: Charles Bennett 3:40 pm Self-testing of universal and fault-tolerant sets of quantum gates Wim van Dam, Frederic Magniez, Michele Mosca, and Miklos Santha 4:05 pm Computing with highly mixed states Andris Ambainis, Leonard J Schulman, and Umesh V Vazirani 4:30 pm Quantum bit escrow Dorit Aharonov, Amnon Ta-Shma, Umesh Vazirani and Andrew C Yao 4:55 pm A proof of security of quantum key distribution Eli Biham, Michel Boyer, P Oscar Boykin, Tal Mor, and Vwani Roychowdhury Sessions 12B Chair: Andrei Broder 3:40 pm Better algorithms for unfair metrical task systems and applications Amos Fiat and Manor Mendel 4:05 pm A unified approach to approximating resource allocation and scheduling Amotz Bar-Noy, Reuven Bar-Yehuda, Ari Freund, Joseph Se Naor, and Baruch Schieber 4:30 pm Balanced allocations: the heavily loaded case Petra Berenbrink, Artur Czumaj, Angelika Steger, Berthold Vocking End of Program