29. STOC 1997: El Paso, Texas, USA

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
  

Last update Fri May 25 08:42:18 2012 CET by the DBLP Team — Data released under the ODC-BY 1.0 license — See also our legal information page