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