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
Johan Håstad:
Some Optimal Inapproximability Results. 1-10Sanjeev Khanna, Madhu Sudan, David P. Williamson:
A Complete Classification of the Approximability of Maximization Problems Derived from Boolean Constraint Satisfaction. 11-20Luca 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-39Joe Buhler, Mohammad Amin Shokrollahi, Volker Stemann:
Fast and Precise Computations of Discrete Fourier Transforms Using Cyclotomic Integers. 40-47Robert 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-65Richard 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-85Ramamohan 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-119Jeff Edmonds, Donald D. Chinn, Tim Brecht, Xiaotie Deng:
Non-clairvoyant Multiprocessor Scheduling of Jobs with Changing Execution Characteristics (Extended Abstract). 120-129Susanne Albers:
Better Bounds for Online Scheduling. 130-139Cynthia 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-159John D. Lafferty, Daniel N. Rockmore:
Spectral Techniques for Expander Codes. 160-167Victor Y. Pan:
Faster Solution of the Key Equation for Decoding BCH Error-Correcting Codes. 168-175Dorit 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-199Zhi-Zhong Chen, Ming-Yang Kao:
Reducing Randomness via Irrational Numbers. 200-209Ketan Mulmuley:
Is There an Algebraic Proof for P != NC? (Extended Abstract). 210-219Russell Impagliazzo, Avi Wigderson:
P = BPP if E Requires Exponential Circuits: Derandomizing the XOR Lemma. 220-229Roy 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-249Peter A. Beling, Sushil Verma:
Combinatorial Complexity of the Central Curve. 250-255Rong-chii Duh, Martin Fürer:
Approximation of k-Set Cover by Semi-Local Optimization. 256-264David B. Shmoys, Éva Tardos, Karen Aardal:
Approximation Algorithms for Facility Location Problems (Extended Abstract). 265-274Tetsuo 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-293Rafail Ostrovsky, Victor Shoup:
Private Information Storage (Extended Abstract). 294-303Benny 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-323Shai Ben-David, Nader H. Bshouty, Eyal Kushilevitz:
A Composition Theorem for Learning Algorithms with Applications to Geometric Concept Classes. 324-333Yoav 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-353Baruch 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-372Martin 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-405Oded Goldreich, Dana Ron:
Property Testing in Bounded Degree Graphs. 406-415Susanne Albers, Monika Rauch Henzinger:
Exploring Unknown Environments. 416-425Xin 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-445Donald Beaver:
Commodity-Based Cryptography (Extended Abstract). 446-455Daniele Micciancio:
Oblivious Data Structures: Applications to Cryptography. 456-464Noga 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-484Sanjeev Arora, Madhu Sudan:
Improved Low-Degree Testing and its Applications. 485-495Joe Kilian, Erez Petrank, Gábor Tardos:
Probabilistically Checkable Proofs with Zero Knowledge. 496-505Uriel 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-530Andrei Z. Broder, Alan M. Frieze, Eli Upfal:
Static and Dynamic Path Selection on Expander Graphs: A Random Walk Approach (Preliminary Version). 531-539Lars Arge, Paolo Ferragina, Roberto Grossi, Jeffrey Scott Vitter:
On Sorting Strings in External Memory (Extended Abstract). 540-548Noam 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-568Dahlia Malkhi, Michael K. Reiter:
Byzantine Quorum Systems. 569-578Wai-Kau Lo, Vassos Hadzilacos:
All of Us are Smarter Than Any of Us: Wait-Free Hierarchies are not Robust. 579-588Maurice 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-608Kenneth L. Clarkson:
Nearest Neighbor Queries in Metric Spaces. 609-617Piotr Indyk, Rajeev Motwani, Prabhakar Raghavan, Santosh Vempala:
Locality-Preserving Hashing in Multidimensional Spaces. 618-625Moses 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-643Rafail Ostrovsky, Yuval Rabani:
Universal O(Congestion + Dilation + log1+epsilonN) Local Control Packet Switching Algorithms. 644-653David 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-663Jon 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-681Michael Luby, Eric Vigoda:
Approximately Counting Up To Four (Extended Abstract). 682-687James Allen Fill:
An Interruptible Algorithm for Perfect Sampling via Markov Chains. 688-695Ravi Kannan, Santosh Vempala:
Sampling Lattice Points. 696-700
Session 11A
Sandy Irani:
Page Replacement with Multi-Size Pages and Applications to Web Caching. 701-710Yair 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-729Manindra Agrawal, Eric Allender, Russell Impagliazzo, Toniann Pitassi, Steven Rudich:
Reducing the Complexity of Reductions. 730-738Alexander 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. 749Lance Fortnow, Michael Sipser:
Retraction of Probabilistic Computation and Linear Time. 750
last updated on 2019-10-22 23:21 CEST by the dblp team
data released under the ODC-BY 1.0 license
see also: Terms of Use | Privacy Policy | Imprint
the dblp computer science bibliography is funded by:
