The SCEAS System
Navigation Menu

Conferences in DBLP

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

  1. Johan Håstad
    Some Optimal Inapproximability Results. [Citation Graph (0, 0)][DBLP]
    STOC, 1997, pp:1-10 [Conf]
  2. Sanjeev Khanna, Madhu Sudan, David P. Williamson
    A Complete Classification of the Approximability of Maximization Problems Derived from Boolean Constraint Satisfaction. [Citation Graph (0, 0)][DBLP]
    STOC, 1997, pp:11-20 [Conf]
  3. Luca Trevisan
    When Hamming Meets Euclid: The Approximability of Geometric TSP and MST (Extended Abstract). [Citation Graph (0, 0)][DBLP]
    STOC, 1997, pp:21-29 [Conf]
  4. John H. Reif
    Approximate Complex Polynomial Evaluation in Near Constant Work Per Point. [Citation Graph (0, 0)][DBLP]
    STOC, 1997, pp:30-39 [Conf]
  5. Joe Buhler, Mohammad Amin Shokrollahi, Volker Stemann
    Fast and Precise Computations of Discrete Fourier Transforms Using Cyclotomic Integers. [Citation Graph (0, 0)][DBLP]
    STOC, 1997, pp:40-47 [Conf]
  6. Robert Beals
    Quantum Computation of Fourier Transforms over Symmetric Groups. [Citation Graph (0, 0)][DBLP]
    STOC, 1997, pp:48-53 [Conf]
  7. Ming-Yang Kao, Tak Wah Lam, Teresa M. Przytycka, Wing-Kin Sung, Hing-Fung Ting
    General Techniques for Comparing Unrooted Evolutionary Trees. [Citation Graph (0, 0)][DBLP]
    STOC, 1997, pp:54-65 [Conf]
  8. Richard Cole, Ramesh Hariharan
    Tree Pattern Matching and Subset Matching in Randomized O(n log3m) Time. [Citation Graph (0, 0)][DBLP]
    STOC, 1997, pp:66-75 [Conf]
  9. Dima Grigoriev, Marek Karpinski
    Randomized Omega(n2) Lower Bound for Knapsack. [Citation Graph (0, 0)][DBLP]
    STOC, 1997, pp:76-85 [Conf]
  10. Ramamohan Paturi, Michael E. Saks, Francis Zane
    Exponential Lower Bounds for Depth 3 Boolean Circuits. [Citation Graph (0, 0)][DBLP]
    STOC, 1997, pp:86-91 [Conf]
  11. Alexander Vardy
    Algorithmic Complexity in Coding Theory and the Minimum Distance Problem. [Citation Graph (0, 0)][DBLP]
    STOC, 1997, pp:92-109 [Conf]
  12. Stefano Leonardi, Danny Raz
    Approximating Total Flow Time on Parallel Machines. [Citation Graph (1, 0)][DBLP]
    STOC, 1997, pp:110-119 [Conf]
  13. Jeff Edmonds, Donald D. Chinn, Tim Brecht, Xiaotie Deng
    Non-clairvoyant Multiprocessor Scheduling of Jobs with Changing Execution Characteristics (Extended Abstract). [Citation Graph (0, 0)][DBLP]
    STOC, 1997, pp:120-129 [Conf]
  14. Susanne Albers
    Better Bounds for Online Scheduling. [Citation Graph (0, 0)][DBLP]
    STOC, 1997, pp:130-139 [Conf]
  15. Cynthia A. Phillips, Clifford Stein, Eric Torng, Joel Wein
    Optimal Time-Critical Scheduling via Resource Augmentation (Extended Abstract). [Citation Graph (0, 0)][DBLP]
    STOC, 1997, pp:140-149 [Conf]
  16. Michael Luby, Michael Mitzenmacher, Mohammad Amin Shokrollahi, Daniel A. Spielman, Volker Stemann
    Practical Loss-Resilient Codes. [Citation Graph (0, 0)][DBLP]
    STOC, 1997, pp:150-159 [Conf]
  17. John D. Lafferty, Daniel N. Rockmore
    Spectral Techniques for Expander Codes. [Citation Graph (0, 0)][DBLP]
    STOC, 1997, pp:160-167 [Conf]
  18. Victor Y. Pan
    Faster Solution of the Key Equation for Decoding BCH Error-Correcting Codes. [Citation Graph (0, 0)][DBLP]
    STOC, 1997, pp:168-175 [Conf]
  19. Dorit Aharonov, Michael Ben-Or
    Fault-Tolerant Quantum Computation With Constant Error. [Citation Graph (0, 0)][DBLP]
    STOC, 1997, pp:176-188 [Conf]
  20. Moni Naor, Omer Reingold
    On the Construction of Pseudo-Random Permutations: Luby-Rackoff Revisited (Extended Abstract). [Citation Graph (0, 0)][DBLP]
    STOC, 1997, pp:189-199 [Conf]
  21. Zhi-Zhong Chen, Ming-Yang Kao
    Reducing Randomness via Irrational Numbers. [Citation Graph (0, 0)][DBLP]
    STOC, 1997, pp:200-209 [Conf]
  22. Ketan Mulmuley
    Is There an Algebraic Proof for P != NC? (Extended Abstract). [Citation Graph (0, 0)][DBLP]
    STOC, 1997, pp:210-219 [Conf]
  23. Russell Impagliazzo, Avi Wigderson
    P = BPP if E Requires Exponential Circuits: Derandomizing the XOR Lemma. [Citation Graph (0, 0)][DBLP]
    STOC, 1997, pp:220-229 [Conf]
  24. Roy Armoni, Amnon Ta-Shma, Avi Wigderson, Shiyu Zhou
    SL <= L4/3. [Citation Graph (0, 0)][DBLP]
    STOC, 1997, pp:230-239 [Conf]
  25. David R. Karger
    Using Random Sampling to Find Maximum Flows in Uncapacitated Undirected Graphs. [Citation Graph (0, 0)][DBLP]
    STOC, 1997, pp:240-249 [Conf]
  26. Peter A. Beling, Sushil Verma
    Combinatorial Complexity of the Central Curve. [Citation Graph (0, 0)][DBLP]
    STOC, 1997, pp:250-255 [Conf]
  27. Rong-chii Duh, Martin Fürer
    Approximation of k-Set Cover by Semi-Local Optimization. [Citation Graph (0, 0)][DBLP]
    STOC, 1997, pp:256-264 [Conf]
  28. David B. Shmoys, Éva Tardos, Karen Aardal
    Approximation Algorithms for Facility Location Problems (Extended Abstract). [Citation Graph (1, 0)][DBLP]
    STOC, 1997, pp:265-274 [Conf]
  29. Tetsuo Asano, Naoki Katoh, Hisao Tamaki, Takeshi Tokuyama
    Covering Points in the Plane by k-Tours: Towards a Polynomial Time Approximation Scheme for General k. [Citation Graph (0, 0)][DBLP]
    STOC, 1997, pp:275-283 [Conf]
  30. Miklós Ajtai, Cynthia Dwork
    A Public-Key Cryptosystem with Worst-Case/Average-Case Equivalence. [Citation Graph (0, 0)][DBLP]
    STOC, 1997, pp:284-293 [Conf]
  31. Rafail Ostrovsky, Victor Shoup
    Private Information Storage (Extended Abstract). [Citation Graph (0, 0)][DBLP]
    STOC, 1997, pp:294-303 [Conf]
  32. Benny Chor, Niv Gilboa
    Computationally Private Information Retrieval (Extended Abstract). [Citation Graph (0, 0)][DBLP]
    STOC, 1997, pp:304-313 [Conf]
  33. Peter Auer, Philip M. Long, Aravind Srinivasan
    Approximating Hyper-Rectangles: Learning and Pseudo-Random Sets. [Citation Graph (0, 0)][DBLP]
    STOC, 1997, pp:314-323 [Conf]
  34. Shai Ben-David, Nader H. Bshouty, Eyal Kushilevitz
    A Composition Theorem for Learning Algorithms with Applications to Geometric Concept Classes. [Citation Graph (0, 0)][DBLP]
    STOC, 1997, pp:324-333 [Conf]
  35. Yoav Freund, Robert E. Schapire, Yoram Singer, Manfred K. Warmuth
    Using and Combining Predictors That Specialize. [Citation Graph (0, 0)][DBLP]
    STOC, 1997, pp:334-343 [Conf]
  36. Piotr Berman, Chris Coulston
    On-Line Algorithms for Steiner Tree Problems (Extended Abstract). [Citation Graph (0, 0)][DBLP]
    STOC, 1997, pp:344-353 [Conf]
  37. Baruch Awerbuch, Tripurari Singh
    Online Algorithms for Selective Multicast and Maximal Dense Trees. [Citation Graph (0, 0)][DBLP]
    STOC, 1997, pp:354-362 [Conf]
  38. Itzhak Parnafes, Ran Raz, Avi Wigderson
    Direct Product Results and the GCD Problem, in Old and New Communication Models. [Citation Graph (0, 0)][DBLP]
    STOC, 1997, pp:363-372 [Conf]
  39. Martin Dietzfelbinger
    The Linear-Array Problem in Communication Complexity Resolved. [Citation Graph (0, 0)][DBLP]
    STOC, 1997, pp:373-382 [Conf]
  40. László Babai
    Paul Erdös (1913-1996): His Influence on the Theory of Computing. [Citation Graph (0, 0)][DBLP]
    STOC, 1997, pp:383-401 [Conf]
  41. William McCuaig, Neil Robertson, Paul D. Seymour, Robin Thomas
    Permanents, Pfaffian Orientations, and Even Directed Circuits (Extended Abstract). [Citation Graph (0, 0)][DBLP]
    STOC, 1997, pp:402-405 [Conf]
  42. Oded Goldreich, Dana Ron
    Property Testing in Bounded Degree Graphs. [Citation Graph (0, 0)][DBLP]
    STOC, 1997, pp:406-415 [Conf]
  43. Susanne Albers, Monika Rauch Henzinger
    Exploring Unknown Environments. [Citation Graph (0, 0)][DBLP]
    STOC, 1997, pp:416-425 [Conf]
  44. Xin He
    On Floorplans of Planar Graphs. [Citation Graph (0, 0)][DBLP]
    STOC, 1997, pp:426-435 [Conf]
  45. Ronald Cramer, Ivan Damgård
    Linear Zero-Knowledge - A Note on Efficient Zero-Knowledge Proofs and Arguments. [Citation Graph (0, 0)][DBLP]
    STOC, 1997, pp:436-445 [Conf]
  46. Donald Beaver
    Commodity-Based Cryptography (Extended Abstract). [Citation Graph (0, 0)][DBLP]
    STOC, 1997, pp:446-455 [Conf]
  47. Daniele Micciancio
    Oblivious Data Structures: Applications to Cryptography. [Citation Graph (0, 0)][DBLP]
    STOC, 1997, pp:456-464 [Conf]
  48. Noga Alon, Martin Dietzfelbinger, Peter Bro Miltersen, Erez Petrank, Gábor Tardos
    Is Linear Hashing Good? [Citation Graph (0, 0)][DBLP]
    STOC, 1997, pp:465-474 [Conf]
  49. Ran Raz, Shmuel Safra
    A Sub-Constant Error-Probability Low-Degree Test, and a Sub-Constant Error-Probability PCP Characterization of NP. [Citation Graph (0, 0)][DBLP]
    STOC, 1997, pp:475-484 [Conf]
  50. Sanjeev Arora, Madhu Sudan
    Improved Low-Degree Testing and its Applications. [Citation Graph (0, 0)][DBLP]
    STOC, 1997, pp:485-495 [Conf]
  51. Joe Kilian, Erez Petrank, Gábor Tardos
    Probabilistically Checkable Proofs with Zero Knowledge. [Citation Graph (0, 0)][DBLP]
    STOC, 1997, pp:496-505 [Conf]
  52. Uriel Feige, Joe Kilian
    Making Games Short (Extended Abstract). [Citation Graph (0, 0)][DBLP]
    STOC, 1997, pp:506-516 [Conf]
  53. Bruce M. Maggs, Berthold Vöcking
    Improved Routing and Sorting on Multibutterflies. [Citation Graph (0, 0)][DBLP]
    STOC, 1997, pp:517-530 [Conf]
  54. Andrei Z. Broder, Alan M. Frieze, Eli Upfal
    Static and Dynamic Path Selection on Expander Graphs: A Random Walk Approach (Preliminary Version). [Citation Graph (0, 0)][DBLP]
    STOC, 1997, pp:531-539 [Conf]
  55. Lars Arge, Paolo Ferragina, Roberto Grossi, Jeffrey Scott Vitter
    On Sorting Strings in External Memory (Extended Abstract). [Citation Graph (1, 0)][DBLP]
    STOC, 1997, pp:540-548 [Conf]
  56. Noam Nisan, Ziv Bar-Yossef
    Pointer Jumping Requires Concurrent Read. [Citation Graph (0, 0)][DBLP]
    STOC, 1997, pp:549-558 [Conf]
  57. James Aspnes
    Lower Bounds for Distributed Coin-Flipping and Randomized Consensus. [Citation Graph (0, 0)][DBLP]
    STOC, 1997, pp:559-568 [Conf]
  58. Dahlia Malkhi, Michael K. Reiter
    Byzantine Quorum Systems. [Citation Graph (0, 0)][DBLP]
    STOC, 1997, pp:569-578 [Conf]
  59. Wai-Kau Lo, Vassos Hadzilacos
    All of Us are Smarter Than Any of Us: Wait-Free Hierarchies are not Robust. [Citation Graph (0, 0)][DBLP]
    STOC, 1997, pp:579-588 [Conf]
  60. Maurice Herlihy, Sergio Rajsbaum
    The Decidability of Distributed Decision Tasks (Extended Abstract). [Citation Graph (0, 0)][DBLP]
    STOC, 1997, pp:589-598 [Conf]
  61. Jon M. Kleinberg
    Two Algorithms for Nearest-Neighbor Search in High Dimensions. [Citation Graph (1, 0)][DBLP]
    STOC, 1997, pp:599-608 [Conf]
  62. Kenneth L. Clarkson
    Nearest Neighbor Queries in Metric Spaces. [Citation Graph (0, 0)][DBLP]
    STOC, 1997, pp:609-617 [Conf]
  63. Piotr Indyk, Rajeev Motwani, Prabhakar Raghavan, Santosh Vempala
    Locality-Preserving Hashing in Multidimensional Spaces. [Citation Graph (1, 0)][DBLP]
    STOC, 1997, pp:618-625 [Conf]
  64. Moses Charikar, Chandra Chekuri, Tomás Feder, Rajeev Motwani
    Incremental Clustering and Dynamic Information Retrieval. [Citation Graph (0, 0)][DBLP]
    STOC, 1997, pp:626-635 [Conf]
  65. Aravind Srinivasan, Chung-Piaw Teo
    A Constant-Factor Approximation Algorithm for Packet Routing, and Balancing Local vs. Global Criteria. [Citation Graph (0, 0)][DBLP]
    STOC, 1997, pp:636-643 [Conf]
  66. Rafail Ostrovsky, Yuval Rabani
    Universal O(Congestion + Dilation + log1+epsilonN) Local Control Packet Switching Algorithms. [Citation Graph (0, 0)][DBLP]
    STOC, 1997, pp:644-653 [Conf]
  67. David R. Karger, Eric Lehman, Frank Thomson Leighton, Rina Panigrahy, Matthew S. Levine, Daniel Lewin
    Consistent Hashing and Random Trees: Distributed Caching Protocols for Relieving Hot Spots on the World Wide Web. [Citation Graph (0, 0)][DBLP]
    STOC, 1997, pp:654-663 [Conf]
  68. Jon M. Kleinberg, Yuval Rabani, Éva Tardos
    Allocating Bandwidth for Bursty Connections. [Citation Graph (0, 0)][DBLP]
    STOC, 1997, pp:664-673 [Conf]
  69. Vivek Gore, Mark Jerrum
    The Swendsen-Wang Process Does Not Always Mix Rapidly. [Citation Graph (0, 0)][DBLP]
    STOC, 1997, pp:674-681 [Conf]
  70. Michael Luby, Eric Vigoda
    Approximately Counting Up To Four (Extended Abstract). [Citation Graph (0, 0)][DBLP]
    STOC, 1997, pp:682-687 [Conf]
  71. James Allen Fill
    An Interruptible Algorithm for Perfect Sampling via Markov Chains. [Citation Graph (0, 0)][DBLP]
    STOC, 1997, pp:688-695 [Conf]
  72. Ravi Kannan, Santosh Vempala
    Sampling Lattice Points. [Citation Graph (0, 0)][DBLP]
    STOC, 1997, pp:696-700 [Conf]
  73. Sandy Irani
    Page Replacement with Multi-Size Pages and Applications to Web Caching. [Citation Graph (0, 0)][DBLP]
    STOC, 1997, pp:701-710 [Conf]
  74. Yair Bartal, Avrim Blum, Carl Burch, Andrew Tomkins
    A polylog(n)-Competitive Algorithm for Metrical Task Systems. [Citation Graph (0, 0)][DBLP]
    STOC, 1997, pp:711-719 [Conf]
  75. Alexis Maciel, Toniann Pitassi
    On ACC0[pk] Frege Proofs. [Citation Graph (0, 0)][DBLP]
    STOC, 1997, pp:720-729 [Conf]
  76. Manindra Agrawal, Eric Allender, Russell Impagliazzo, Toniann Pitassi, Steven Rudich
    Reducing the Complexity of Reductions. [Citation Graph (0, 0)][DBLP]
    STOC, 1997, pp:730-738 [Conf]
  77. Alexander A. Razborov, Avi Wigderson, Andrew Chi-Chih Yao
    Read-Once Branching Programs, Rectangular Proofs of the Pigeonhole Principle and the Transversal Calculus. [Citation Graph (0, 0)][DBLP]
    STOC, 1997, pp:739-748 [Conf]
  78. Fan R. K. Chung, S.-T. Yau
    Eigenvalues, Flows and Separators of Graphs. [Citation Graph (0, 0)][DBLP]
    STOC, 1997, pp:749- [Conf]
  79. Lance Fortnow, Michael Sipser
    Retraction of Probabilistic Computation and Linear Time. [Citation Graph (0, 0)][DBLP]
    STOC, 1997, pp:750- [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