default search action
Google
Google Scholar
Semantic Scholar
Internet Archive Scholar
CiteSeerX
ORCID29th 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
- Johan Håstad:
Some Optimal Inapproximability Results. 1-10 - 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
- John H. Reif:
Approximate Complex Polynomial Evaluation in Near Constant Work Per Point. 30-39 - Joe Buhler, Mohammad Amin Shokrollahi, Volker Stemann:
Fast and Precise Computations of Discrete Fourier Transforms Using Cyclotomic Integers. 40-47 - Robert Beals:
Quantum Computation of Fourier Transforms over Symmetric Groups. 48-53
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
- Dima Grigoriev, Marek Karpinski:
Randomized Omega(n2) Lower Bound for Knapsack. 76-85 - Ramamohan Paturi, Michael E. Saks, Francis Zane:
Exponential Lower Bounds for Depth 3 Boolean Circuits. 86-91
Invited Session I
- Alexander Vardy:
Algorithmic Complexity in Coding Theory and the Minimum Distance Problem. 92-109
Session 3A
- Stefano Leonardi, Danny Raz:
Approximating Total Flow Time on Parallel Machines. 110-119 - Jeff Edmonds, Donald D. Chinn, Tim Brecht, Xiaotie Deng:
Non-clairvoyant Multiprocessor Scheduling of Jobs with Changing Execution Characteristics (Extended Abstract). 120-129 - Susanne Albers:
Better Bounds for Online Scheduling. 130-139 - 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 - John D. Lafferty, Daniel N. Rockmore:
Spectral Techniques for Expander Codes. 160-167 - Victor Y. Pan:
Faster Solution of the Key Equation for Decoding BCH Error-Correcting Codes. 168-175 - Dorit Aharonov, Michael Ben-Or
:
Fault-Tolerant Quantum Computation With Constant Error. 176-188
Session 4A
- Moni Naor, Omer Reingold:
On the Construction of Pseudo-Random Permutations: Luby-Rackoff Revisited (Extended Abstract). 189-199 - Zhi-Zhong Chen, Ming-Yang Kao:
Reducing Randomness via Irrational Numbers. 200-209 - Ketan Mulmuley:
Is There an Algebraic Proof for P != NC? (Extended Abstract). 210-219 - Russell Impagliazzo, Avi Wigderson:
P = BPP if E Requires Exponential Circuits: Derandomizing the XOR Lemma. 220-229 - Roy Armoni, Amnon Ta-Shma, Avi Wigderson, Shiyu Zhou:
SL <= L4/3. 230-239
Session 4B
- David R. Karger:
Using Random Sampling to Find Maximum Flows in Uncapacitated Undirected Graphs. 240-249 - Peter A. Beling, Sushil Verma:
Combinatorial Complexity of the Central Curve. 250-255 - Rong-chii Duh, Martin Fürer:
Approximation of k-Set Cover by Semi-Local Optimization. 256-264 - David B. Shmoys, Éva Tardos, Karen I. 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 - Rafail Ostrovsky, Victor Shoup:
Private Information Storage (Extended Abstract). 294-303 - Benny Chor, Niv Gilboa:
Computationally Private Information Retrieval (Extended Abstract). 304-313
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 - Martin Dietzfelbinger:
The Linear-Array Problem in Communication Complexity Resolved. 373-382
Invited Session II
- László Babai:
Paul Erdös (1913-1996): His Influence on the Theory of Computing. 383-401
Session 7A
- William McCuaig, Neil Robertson, Paul D. Seymour, Robin Thomas:
Permanents, Pfaffian Orientations, and Even Directed Circuits (Extended Abstract). 402-405 - Oded Goldreich, Dana Ron:
Property Testing in Bounded Degree Graphs. 406-415 - Susanne Albers, Monika Rauch Henzinger:
Exploring Unknown Environments. 416-425 - Xin He:
On Floorplans of Planar Graphs. 426-435
Session 7B
- Ronald Cramer, Ivan Damgård:
Linear Zero-Knowledge - A Note on Efficient Zero-Knowledge Proofs and Arguments. 436-445 - Donald Beaver:
Commodity-Based Cryptography (Extended Abstract). 446-455 - Daniele Micciancio:
Oblivious Data Structures: Applications to Cryptography. 456-464 - 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 - Sanjeev Arora, Madhu Sudan:
Improved Low-Degree Testing and its Applications. 485-495 - Joe Kilian, Erez Petrank, Gábor Tardos:
Probabilistically Checkable Proofs with Zero Knowledge. 496-505 - Uriel Feige, Joe Kilian:
Making Games Short (Extended Abstract). 506-516
Session 8B
- Bruce M. Maggs, Berthold Vöcking:
Improved Routing and Sorting on Multibutterflies. 517-530 - 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 - Noam Nisan, Ziv Bar-Yossef:
Pointer Jumping Requires Concurrent Read. 549-558
Session 9A
- James Aspnes:
Lower Bounds for Distributed Coin-Flipping and Randomized Consensus. 559-568 - Dahlia Malkhi, Michael K. Reiter:
Byzantine Quorum Systems. 569-578 - 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
- Jon M. Kleinberg:
Two Algorithms for Nearest-Neighbor Search in High Dimensions. 599-608 - Kenneth L. Clarkson:
Nearest Neighbor Queries in Metric Spaces. 609-617 - Piotr Indyk, Rajeev Motwani, Prabhakar Raghavan, Santosh S. 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 - Jon M. Kleinberg, Yuval Rabani, Éva Tardos:
Allocating Bandwidth for Bursty Connections. 664-673
Session 10B
- Vivek Gore, Mark Jerrum:
The Swendsen-Wang Process Does Not Always Mix Rapidly. 674-681 - Michael Luby, Eric Vigoda:
Approximately Counting Up To Four (Extended Abstract). 682-687 - James Allen Fill:
An Interruptible Algorithm for Perfect Sampling via Markov Chains. 688-695 - Ravi Kannan, Santosh S. Vempala:
Sampling Lattice Points. 696-700
Session 11A
- Sandy Irani:
Page Replacement with Multi-Size Pages and Applications to Web Caching. 701-710 - Yair Bartal, Avrim Blum, Carl Burch, Andrew Tomkins:
A polylog(n)-Competitive Algorithm for Metrical Task Systems. 711-719
Session 11B
- Alexis Maciel, Toniann Pitassi:
On ACC0[pk] Frege Proofs. 720-729 - 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
- Fan R. K. Chung, Shing-Tung Yau:
Eigenvalues, Flows and Separators of Graphs. 749 - Lance Fortnow, Michael Sipser:
Retraction of Probabilistic Computation and Linear Time. 750
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-11-07 20:38 CET 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:
