F. Frances Yao, Eugene M. Luks (Eds.):
Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing, May 21-23, 2000, Portland, OR, USA.
ACM 2000, ISBN 1-58113-184-4
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
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
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
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
Vadim Olshevsky, Mohammad Amin Shokrollahi: Matrix-vector product for confluent Cauchy-like matrices with application to confluent rational interpolation.
573-581