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