32. STOC 2000: Portland, Oregon, USA

• Russell Impagliazzo, Ronen Shaltiel, Avi Wigderson:
  Extractors and pseudo-random generators with optimal seed length. 1-10
  
• Moni Naor, Omer Reingold, Alon Rosen:
  Pseudo-random functions and factoring (extended abstract). 11-20
  
• Claudio Gutiérrez:
  Satisfiability of equations in free groups is in PSPACE. 21-27
  
• Dimitris Achlioptas:
  Setting 2 variables at a time yields a new lower bound for random 3-SAT (extended abstract). 28-37
  
• Artur Czumaj, Christian Scheideler:
  A new algorithm approach to the general Lovász local lemma with applications to scheduling and satisfiability problems (extended abstract). 38-47
  
• Leonid Gurvits, Alex Samorodnitsky:
  A deterministic polynomial-time algorithm for approximating mixed discriminant and mixed volume. 48-57
  
• Robert D. Carr, Santosh Vempala:
  Randomized metarounding (extended abstract). 58-62
  
• Martin Grohe:
  Isomorphism testing for embeddable graphs through definability. 63-72
  
• Valentine Kabanets, Jin-yi Cai:
  Circuit minimization problem. 73-79
  
• Jonathan Katz, Luca Trevisan:
  On the efficiency of local decoding procedures for error-correcting codes. 80-86
  
• Sorin Istrail:
  Statistical mechanics, three-dimensionality and NP-completeness: I. Universality of intracatability for the partition function of the Ising model across non-planar surfaces (extended abstract). 87-96
  
• Satoru Iwata, Lisa Fleischer, Satoru Fujishige:
  A combinatorial, strongly polynomial-time algorithm for minimizing submodular functions. 97-106
  
• Lisa Fleischer, Satoru Iwata:
  Improved algorithms for submodular function minimization and submodular flow. 107-116
  
• Jens Vygen:
  On dual minimum cost flow algorithms (extended abstract). 117-125
  
• Christos H. Papadimitriou, Santosh Vempala:
  On the approximability of the traveling salesman problem (extended abstract). 126-133
  
• Uriel Feige, Magnús M. Halldórsson, Guy Kortsarz:
  Approximating the domatic number. 134-143
  
• Aravind Srinivasan:
  The value of strong inapproximability results for clique. 144-152
  
• Micah Adler, Frank Thomson Leighton:
  Compression using efficient multicasting. 153-162
  
• Jon M. Kleinberg:
  The small-world phenomenon: an algorithm perspective. 163-170
  
• William Aiello, Fan R. K. Chung, Linyuan Lu:
  A random graph model for massive graphs. 171-180
  
• Venkatesan Guruswami, Madhu Sudan:
  List decoding algorithms for certain concatenated codes. 181-190
  
• Alex Samorodnitsky, Luca Trevisan:
  A PCP characterization of NP with optimal amortized query complexity. 191-199
  
• Salil P. Vadhan:
  On transformation of interactive proofs that preserve the prover's complexity. 200-207
  
• János Csirik, David S. Johnson, Claire Kenyon, James B. Orlin, Peter W. Shor, Richard R. Weber:
  On the sum-of-squares algorithm for bin packing. 208-217
  
• Joan Feigenbaum, Christos H. Papadimitriou, Scott Shenker:
  Sharing the cost of muliticast transmissions (preliminary version). 218-227
  
• Ming-Yang Kao, Andreas Nolte, Stephen R. Tate:
  The risk profile problem for stock portfolio optimization (extended abstract). 228-234
  
• Ran Canetti, Oded Goldreich, Shafi Goldwasser, Silvio Micali:
  Resettable zero-knowledge (extended abstract). 235-244
  
• Jonathan Katz, Moti Yung:
  Complete characterization of security notions for probabilistic private-key encryption. 245-254
  
• Giovanni Di Crescenzo, Kouichi Sakurai, Moti Yung:
  On zero-knowledge proofs (extended abstract): ``from membership to decision''. 255-264
  
• Dan Boneh:
  Finding smooth integers in short intervals using CRT decoding. 265-272
  
• Herbert Edelsbrunner, Xiang-Yang Li, Gary L. Miller, Andreas Stathopoulos, Dafna Talmor, Shang-Hua Teng, Alper Üngör, Noel Walkington:
  Smoothing and cleaning up slivers. 273-277
  
• Costas Busch, Maurice Herlihy, Roger Wattenhofer:
  Hard-Potato routing. 278-285
  
• Lyudmil Aleksandrov, Anil Maheshwari, Jörg-Rüdiger Sack:
  Approximation algorithms for geometric shortest path problems. 286-295
  
• Guy Even, Sudipto Guha, Baruch Schieber:
  Improved approximations of crossings in graph drawings. 296-305
  
• Rajeev Motwani, Rina Panigrahy, Vijay A. Saraswat, Suresh Venkatasubramanian:
  On the decidability of accessibility problems (extended abstract). 306-315
  
• Joe Kilian:
  More general completeness theorems for secure two-party computation. 316-324
  
• Ronald Cramer, Ivan Damgård, Stefan Dziembowski:
  On the complexity of verifiable secret sharing and multiparty computation. 325-334
  
• Arne Andersson, Mikkel Thorup:
  Tight(er) worst-case bounds on dynamic searching and priority queues. 335-342
  
• Mikkel Thorup:
  Near-optimal fully-dynamic graph connectivity. 343-350
  
• Meena Mahajan, Kasturi R. Varadarajan:
  A new NC-algorithm for finding a perfect matching in bipartite planar and small genus graphs (extended abstract). 351-357
  
• Michael Alekhnovich, Eli Ben-Sasson, Alexander A. Razborov, Avi Wigderson:
  Space complexity in propositional calculus. 358-367
  
• Alexis Maciel, Toniann Pitassi, Alan R. Woods:
  A new proof of the weak pigeonhole principle. 368-377
  
• Danny Harnik, Ran Raz:
  Higher lower bounds on monotone size. 378-387
  
• Omer Barkol, Yuval Rabani:
  Tighter bounds for nearest neighbor search and related problems in the cell probe model. 388-396
  
• Roberto Grossi, Jeffrey Scott Vitter:
  Compressed suffix arrays and suffix trees with applications to text indexing and string matching (extended abstract). 397-406
  
• Richard Cole, Ramesh Hariharan:
  Faster suffix tree construction with missing suffix links. 407-415
  
• S. Muthukrishnan, Süleyman Cenk Sahinalp:
  Approximate nearest neighbors and sequence comparison with block operations. 416-424
  
• Ming Li, Bin Ma, Lusheng Wang:
  Near optimal multiple alignment within a band in polynomial time. 425-434
  
• Avrim Blum, Adam Kalai, Hal Wasserman:
  Noise-tolerant learning, the parity problem, and the statistical query model. 435-440
  
• Judy Goldsmith, Robert H. Sloan:
  More theory revision with queries (extended abstract). 441-448
  
• Harry Buhrman, Peter Bro Miltersen, Jaikumar Radhakrishnan, Srinivasan Venkatesh:
  Are bitvectors optimal? 449-458
  
• Paul W. K. Rothemund, Erik Winfree:
  The program-size complexity of self-assembled squares (extended abstract). 459-468
  
• Danny Z. Chen, Jinhui Xu:
  Shortest path queries in planar graphs. 469-478
  
• Bruce A. Reed:
  How tall is a tree? 479-483
  
• Ronald Fagin, Anna R. Karlin, Jon M. Kleinberg, Prabhakar Raghavan, Sridhar Rajagopalan, Ronitt Rubinfeld, Madhu Sudan, Andrew Tomkins:
  Random walks with ``back buttons'' (extended abstract). 484-493
  
• Matthias Fitzi, Ueli M. Maurer:
  From partial consistency to global broadcast. 494-503
  
• David Kempe, Jon M. Kleinberg, Amit Kumar:
  Connectivity and inference problems for temporal networks. 504-513
  
• April Rasala, Gordon T. Wilfong:
  Strictly non-blocking WDM cross-connects for heterogeneous networks. 514-523
  
• Tomás Feder, Rajeev Motwani, Carlos S. Subi:
  Finding long paths and cycles in sparse Hamiltonian graphs. 524-529
  
• Uriel Feige, Robert Krauthgamer, Kobbi Nissim:
  Approximating the minimum bisection size (extended abstract). 530-536
  
• Jochen Könemann, R. Ravi:
  A matter of degree: improved approximation algorithms for degree-bounded minimum spanning trees. 537-546
  
• Leonard J. Schulman:
  Clustering for edge-cost minimization (extended abstract). 547-555
  
• Steven Fortune:
  Exact computations of the inertia symmetric integer matrices. 556-564
  
• James B. Orlin, Andreas S. Schulz, Sudipta Sengupta:
  epsilon-optimization schemes and L-bit precision: alternative perspectives in combinatorial optimization (extended abstract). 565-572
  
• Vadim Olshevsky, Mohammad Amin Shokrollahi:
  Matrix-vector product for confluent Cauchy-like matrices with application to confluent rational interpolation. 573-581
  
• Moses Charikar, Ronald Fagin, Venkatesan Guruswami, Jon M. Kleinberg, Prabhakar Raghavan, Amit Sahai:
  Query strategies for priced information (extended abstract). 582-591
  
• Steven S. Seiden:
  A guessing game and randomized online algorithms. 592-601
  
• Tomás Feder, Rajeev Motwani, Rina Panigrahy, Chris Olston, Jennifer Widom:
  Computing the median with uncertainty. 602-607
  
• Alexei Kitaev, John Watrous:
  Parallelization, amplification, and exponential time simulation of quantum interactive proof systems. 608-617
  
• Lov K. Grover:
  Rapid sampling though quantum computing. 618-626
  
• Sean Hallgren, Alexander Russell, Amnon Ta-Shma:
  Normal subgroup reconstruction and quantum computation using group representations. 627-635
  
• Andris Ambainis:
  Quantum lower bounds by quantum arguments. 636-643
  
• Hartmut Klauck:
  On quantum and probabilistic communication: Las Vegas and one-way protocols. 644-651
  
• Anupam Gupta, Éva Tardos:
  A constant factor approximation algorithm for a class of classification problems. 652-658
  
• Claire Kenyon, Nicolas Schabanel, Neal E. Young:
  Polynomial-time approximation scheme for data broadcast. 659-666
  
• Martin Fürer:
  Approximating permanents of complex matrices. 667-669
  
• Ashish Goel, Adam Meyerson, Serge A. Plotkin:
  Combining fairness with throughput: online routing with multiple objectives. 670-679
  
• Piotr Berman, Bhaskar DasGupta:
  Improvements in throughout maximization for real-time scheduling. 680-687
  
• Wim van Dam, Frédéric Magniez, Michele Mosca, Miklos Santha:
  Self-testing of universal and fault-tolerant sets of quantum gates. 688-696
  
• Andris Ambainis, Leonard J. Schulman, Umesh V. Vazirani:
  Computing with highly mixed states (extended abstract). 697-704
  
• Dorit Aharonov, Amnon Ta-Shma, Umesh V. Vazirani, Andrew Chi-Chih Yao:
  Quantum bit escrow. 705-714
  
• Eli Biham, Michel Boyer, P. Oscar Boykin, Tal Mor, Vwani P. Roychowdhury:
  A proof of the security of quantum key distribution (extended abstract). 715-724
  
• Amos Fiat, Manor Mendel:
  Better algorithms for unfair metrical task systems and applications. 725-734
  
• Amotz Bar-Noy, Reuven Bar-Yehuda, Ari Freund, Joseph Naor, Baruch Schieber:
  A unified approach to approximating resource allocation and scheduling. 735-744
  
• Petra Berenbrink, Artur Czumaj, Angelika Steger, Berthold Vöcking:
  Balanced allocations: the heavily loaded case. 745-754