Google
Google Scholar
MS Academic
CiteSeerX
CORE
Semantic Scholar29th STOC 1997: El Paso, Texas, USA
Frank Thomson Leighton, Peter W. Shor:
Proceedings of the Twenty-Ninth Annual ACM Symposium on the Theory of Computing, El Paso, Texas, USA, May 4-6, 1997. ACM 1997, ISBN 0-89791-888-6
Session 1A
- Sanjeev Khanna, Madhu Sudan, David P. Williamson:
A Complete Classification of the Approximability of Maximization Problems Derived from Boolean Constraint Satisfaction. 11-20 - Luca Trevisan:
When Hamming Meets Euclid: The Approximability of Geometric TSP and MST (Extended Abstract). 21-29
Session 1B
- Joe Buhler, Mohammad Amin Shokrollahi, Volker Stemann:
Fast and Precise Computations of Discrete Fourier Transforms Using Cyclotomic Integers. 40-47
Session 2A
- Ming-Yang Kao, Tak Wah Lam, Teresa M. Przytycka, Wing-Kin Sung, Hing-Fung Ting:
General Techniques for Comparing Unrooted Evolutionary Trees. 54-65 - Richard Cole, Ramesh Hariharan:
Tree Pattern Matching and Subset Matching in Randomized O(n log3m) Time. 66-75
Session 2B
- Ramamohan Paturi, Michael E. Saks, Francis Zane:
Exponential Lower Bounds for Depth 3 Boolean Circuits. 86-91
Invited Session I
Session 3A
- Jeff Edmonds, Donald D. Chinn, Tim Brecht, Xiaotie Deng:
Non-clairvoyant Multiprocessor Scheduling of Jobs with Changing Execution Characteristics (Extended Abstract). 120-129 - Cynthia A. Phillips, Clifford Stein, Eric Torng, Joel Wein:
Optimal Time-Critical Scheduling via Resource Augmentation (Extended Abstract). 140-149
Session 3B
- Michael Luby, Michael Mitzenmacher, Mohammad Amin Shokrollahi, Daniel A. Spielman, Volker Stemann:
Practical Loss-Resilient Codes. 150-159
Session 4A
- Moni Naor, Omer Reingold:
On the Construction of Pseudo-Random Permutations: Luby-Rackoff Revisited (Extended Abstract). 189-199 - Russell Impagliazzo, Avi Wigderson:
P = BPP if E Requires Exponential Circuits: Derandomizing the XOR Lemma. 220-229
Session 4B
- David R. Karger:
Using Random Sampling to Find Maximum Flows in Uncapacitated Undirected Graphs. 240-249 - David B. Shmoys, Éva Tardos, Karen Aardal:
Approximation Algorithms for Facility Location Problems (Extended Abstract). 265-274 - 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. 275-283
Session 5A
- Miklós Ajtai, Cynthia Dwork:
A Public-Key Cryptosystem with Worst-Case/Average-Case Equivalence. 284-293
Session 5B
- Peter Auer, Philip M. Long, Aravind Srinivasan:
Approximating Hyper-Rectangles: Learning and Pseudo-Random Sets. 314-323 - Shai Ben-David, Nader H. Bshouty, Eyal Kushilevitz:
A Composition Theorem for Learning Algorithms with Applications to Geometric Concept Classes. 324-333 - Yoav Freund, Robert E. Schapire, Yoram Singer, Manfred K. Warmuth:
Using and Combining Predictors That Specialize. 334-343
Session 6A
- Piotr Berman, Chris Coulston:
On-Line Algorithms for Steiner Tree Problems (Extended Abstract). 344-353 - Baruch Awerbuch, Tripurari Singh:
Online Algorithms for Selective Multicast and Maximal Dense Trees. 354-362
Session 6B
- Itzhak Parnafes, Ran Raz, Avi Wigderson:
Direct Product Results and the GCD Problem, in Old and New Communication Models. 363-372
Invited Session II
Session 7A
- William McCuaig, Neil Robertson, Paul D. Seymour, Robin Thomas:
Permanents, Pfaffian Orientations, and Even Directed Circuits (Extended Abstract). 402-405
Session 7B
- Ronald Cramer, Ivan Damgård:
Linear Zero-Knowledge - A Note on Efficient Zero-Knowledge Proofs and Arguments. 436-445 - Noga Alon, Martin Dietzfelbinger, Peter Bro Miltersen, Erez Petrank, Gábor Tardos:
Is Linear Hashing Good? 465-474
Session 8A
- Ran Raz, Shmuel Safra:
A Sub-Constant Error-Probability Low-Degree Test, and a Sub-Constant Error-Probability PCP Characterization of NP. 475-484 - Joe Kilian, Erez Petrank, Gábor Tardos:
Probabilistically Checkable Proofs with Zero Knowledge. 496-505
Session 8B
- Andrei Z. Broder, Alan M. Frieze, Eli Upfal:
Static and Dynamic Path Selection on Expander Graphs: A Random Walk Approach (Preliminary Version). 531-539 - Lars Arge, Paolo Ferragina, Roberto Grossi, Jeffrey Scott Vitter:
On Sorting Strings in External Memory (Extended Abstract). 540-548
Session 9A
- Wai-Kau Lo, Vassos Hadzilacos:
All of Us are Smarter Than Any of Us: Wait-Free Hierarchies are not Robust. 579-588 - Maurice Herlihy, Sergio Rajsbaum:
The Decidability of Distributed Decision Tasks (Extended Abstract). 589-598
Session 9B
- Piotr Indyk, Rajeev Motwani, Prabhakar Raghavan, Santosh Vempala:
Locality-Preserving Hashing in Multidimensional Spaces. 618-625 - Moses Charikar, Chandra Chekuri, Tomás Feder, Rajeev Motwani:
Incremental Clustering and Dynamic Information Retrieval. 626-635
Session 10A
- Aravind Srinivasan, Chung-Piaw Teo:
A Constant-Factor Approximation Algorithm for Packet Routing, and Balancing Local vs. Global Criteria. 636-643 - Rafail Ostrovsky, Yuval Rabani:
Universal O(Congestion + Dilation + log1+epsilonN) Local Control Packet Switching Algorithms. 644-653 - 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. 654-663
Session 10B
Session 11A
- Yair Bartal, Avrim Blum, Carl Burch, Andrew Tomkins:
A polylog(n)-Competitive Algorithm for Metrical Task Systems. 711-719
Session 11B
- Manindra Agrawal, Eric Allender, Russell Impagliazzo, Toniann Pitassi, Steven Rudich:
Reducing the Complexity of Reductions. 730-738 - Alexander A. Razborov, Avi Wigderson, Andrew Chi-Chih Yao:
Read-Once Branching Programs, Rectangular Proofs of the Pigeonhole Principle and the Transversal Calculus. 739-748
Errata
maintained by 
at 
at 
last updated on 2019-01-16 00:25 CET by the dblp team
data released under the ODC-BY 1.0 license
see also: Terms of Use | Privacy Policy | Imprint