29. STOC 1997: El Paso, Texas, USA

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 log³m) Time. 66-75

Session 2B

Dima Grigoriev, Marek Karpinski:
Randomized Omega(n²) 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 <= L^4/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 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 + log^1+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 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 ACC⁰[p^k] 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, S.-T. Yau:
Eigenvalues, Flows and Separators of Graphs. 749
Lance Fortnow, Michael Sipser:
Retraction of Probabilistic Computation and Linear Time. 750