default search action
32nd STOC 2000: Portland, Oregon, USA
- F. Frances Yao, Eugene M. Luks:
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 - 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 Gutierrez:
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 S. 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 S. Vempala:
On the approximability of the traveling salesman problem (extended abstract). 126-133 - Uriel Feige, Magnús M. Halldórsson
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 algorithmic 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
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
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
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 Y. 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
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
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
manage site settings
To protect your privacy, all features that rely on external API calls from your browser are turned off by default. You need to opt-in for them to become active. All settings here will be stored as cookies with your web browser. For more information see our F.A.Q.
last updated on 2024-09-26 23:30 CEST by the dblp team
all metadata released as open data under CC0 1.0 license
see also: Terms of Use | Privacy Policy | Imprint
dblp was originally created in 1993 at:
since 2018, dblp has been operated and maintained by:
the dblp computer science bibliography is funded and supported by: