Stop the war!Остановите войну!
for scientists:
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 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
a service of 
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 2023-06-09 20:53 CEST 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:
