The SCEAS System
Navigation Menu

Conferences in DBLP

Symposium on the Theory of Computing (STOC) (stoc)
2000 (conf/stoc/2000)

  1. 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]
  2. Moni Naor, Omer Reingold, Alon Rosen
    Pseudo-random functions and factoring (extended abstract). [Citation Graph (0, 0)][DBLP]
    STOC, 2000, pp:11-20 [Conf]
  3. Claudio Gutiérrez
    Satisfiability of equations in free groups is in PSPACE. [Citation Graph (0, 0)][DBLP]
    STOC, 2000, pp:21-27 [Conf]
  4. 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]
  5. 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]
  6. 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]
  7. Robert D. Carr, Santosh Vempala
    Randomized metarounding (extended abstract). [Citation Graph (0, 0)][DBLP]
    STOC, 2000, pp:58-62 [Conf]
  8. Martin Grohe
    Isomorphism testing for embeddable graphs through definability. [Citation Graph (0, 0)][DBLP]
    STOC, 2000, pp:63-72 [Conf]
  9. Valentine Kabanets, Jin-yi Cai
    Circuit minimization problem. [Citation Graph (0, 0)][DBLP]
    STOC, 2000, pp:73-79 [Conf]
  10. 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]
  11. 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]
  12. 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]
  13. Lisa Fleischer, Satoru Iwata
    Improved algorithms for submodular function minimization and submodular flow. [Citation Graph (0, 0)][DBLP]
    STOC, 2000, pp:107-116 [Conf]
  14. Jens Vygen
    On dual minimum cost flow algorithms (extended abstract). [Citation Graph (0, 0)][DBLP]
    STOC, 2000, pp:117-125 [Conf]
  15. 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]
  16. Uriel Feige, Magnús M. Halldórsson, Guy Kortsarz
    Approximating the domatic number. [Citation Graph (0, 0)][DBLP]
    STOC, 2000, pp:134-143 [Conf]
  17. Aravind Srinivasan
    The value of strong inapproximability results for clique. [Citation Graph (0, 0)][DBLP]
    STOC, 2000, pp:144-152 [Conf]
  18. Micah Adler, Frank Thomson Leighton
    Compression using efficient multicasting. [Citation Graph (0, 0)][DBLP]
    STOC, 2000, pp:153-162 [Conf]
  19. Jon M. Kleinberg
    The small-world phenomenon: an algorithm perspective. [Citation Graph (0, 0)][DBLP]
    STOC, 2000, pp:163-170 [Conf]
  20. 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]
  21. Venkatesan Guruswami, Madhu Sudan
    List decoding algorithms for certain concatenated codes. [Citation Graph (0, 0)][DBLP]
    STOC, 2000, pp:181-190 [Conf]
  22. 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]
  23. 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]
  24. 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]
  25. 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]
  26. 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]
  27. Ran Canetti, Oded Goldreich, Shafi Goldwasser, Silvio Micali
    Resettable zero-knowledge (extended abstract). [Citation Graph (0, 0)][DBLP]
    STOC, 2000, pp:235-244 [Conf]
  28. 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]
  29. 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]
  30. Dan Boneh
    Finding smooth integers in short intervals using CRT decoding. [Citation Graph (0, 0)][DBLP]
    STOC, 2000, pp:265-272 [Conf]
  31. 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]
  32. Costas Busch, Maurice Herlihy, Roger Wattenhofer
    Hard-Potato routing. [Citation Graph (0, 0)][DBLP]
    STOC, 2000, pp:278-285 [Conf]
  33. 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]
  34. Guy Even, Sudipto Guha, Baruch Schieber
    Improved approximations of crossings in graph drawings. [Citation Graph (0, 0)][DBLP]
    STOC, 2000, pp:296-305 [Conf]
  35. 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]
  36. Joe Kilian
    More general completeness theorems for secure two-party computation. [Citation Graph (0, 0)][DBLP]
    STOC, 2000, pp:316-324 [Conf]
  37. 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]
  38. 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]
  39. Mikkel Thorup
    Near-optimal fully-dynamic graph connectivity. [Citation Graph (0, 0)][DBLP]
    STOC, 2000, pp:343-350 [Conf]
  40. 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]
  41. 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]
  42. 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]
  43. Danny Harnik, Ran Raz
    Higher lower bounds on monotone size. [Citation Graph (0, 0)][DBLP]
    STOC, 2000, pp:378-387 [Conf]
  44. 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]
  45. 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]
  46. Richard Cole, Ramesh Hariharan
    Faster suffix tree construction with missing suffix links. [Citation Graph (0, 0)][DBLP]
    STOC, 2000, pp:407-415 [Conf]
  47. 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]
  48. 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]
  49. 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]
  50. Judy Goldsmith, Robert H. Sloan
    More theory revision with queries (extended abstract). [Citation Graph (0, 0)][DBLP]
    STOC, 2000, pp:441-448 [Conf]
  51. Harry Buhrman, Peter Bro Miltersen, Jaikumar Radhakrishnan, Srinivasan Venkatesh
    Are bitvectors optimal? [Citation Graph (0, 0)][DBLP]
    STOC, 2000, pp:449-458 [Conf]
  52. 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]
  53. Danny Z. Chen, Jinhui Xu
    Shortest path queries in planar graphs. [Citation Graph (0, 0)][DBLP]
    STOC, 2000, pp:469-478 [Conf]
  54. Bruce A. Reed
    How tall is a tree? [Citation Graph (0, 0)][DBLP]
    STOC, 2000, pp:479-483 [Conf]
  55. 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]
  56. Matthias Fitzi, Ueli M. Maurer
    From partial consistency to global broadcast. [Citation Graph (0, 0)][DBLP]
    STOC, 2000, pp:494-503 [Conf]
  57. 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]
  58. 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]
  59. 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]
  60. Uriel Feige, Robert Krauthgamer, Kobbi Nissim
    Approximating the minimum bisection size (extended abstract). [Citation Graph (0, 0)][DBLP]
    STOC, 2000, pp:530-536 [Conf]
  61. 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]
  62. Leonard J. Schulman
    Clustering for edge-cost minimization (extended abstract). [Citation Graph (0, 0)][DBLP]
    STOC, 2000, pp:547-555 [Conf]
  63. Steven Fortune
    Exact computations of the inertia symmetric integer matrices. [Citation Graph (0, 0)][DBLP]
    STOC, 2000, pp:556-564 [Conf]
  64. 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]
  65. 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]
  66. 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]
  67. Steven S. Seiden
    A guessing game and randomized online algorithms. [Citation Graph (0, 0)][DBLP]
    STOC, 2000, pp:592-601 [Conf]
  68. 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]
  69. 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]
  70. Lov K. Grover
    Rapid sampling though quantum computing. [Citation Graph (0, 0)][DBLP]
    STOC, 2000, pp:618-626 [Conf]
  71. 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]
  72. Andris Ambainis
    Quantum lower bounds by quantum arguments. [Citation Graph (0, 0)][DBLP]
    STOC, 2000, pp:636-643 [Conf]
  73. Hartmut Klauck
    On quantum and probabilistic communication: Las Vegas and one-way protocols. [Citation Graph (0, 0)][DBLP]
    STOC, 2000, pp:644-651 [Conf]
  74. 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]
  75. 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]
  76. Martin Fürer
    Approximating permanents of complex matrices. [Citation Graph (0, 0)][DBLP]
    STOC, 2000, pp:667-669 [Conf]
  77. 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]
  78. Piotr Berman, Bhaskar DasGupta
    Improvements in throughout maximization for real-time scheduling. [Citation Graph (0, 0)][DBLP]
    STOC, 2000, pp:680-687 [Conf]
  79. 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]
  80. 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]
  81. 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]
  82. 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]
  83. Amos Fiat, Manor Mendel
    Better algorithms for unfair metrical task systems and applications. [Citation Graph (0, 0)][DBLP]
    STOC, 2000, pp:725-734 [Conf]
  84. 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]
  85. 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]
NOTICE1
System may not be available sometimes or not working properly, since it is still in development with continuous upgrades
NOTICE2
The rankings that are presented on this page should NOT be considered as formal since the citation info is incomplete in DBLP
 
System created by asidirop@csd.auth.gr [http://users.auth.gr/~asidirop/] © 2002
for Data Engineering Laboratory, Department of Informatics, Aristotle University © 2002