28. STOC 1996: Philadephia, Pennsylvania, USA

Session 1A

• Eyal Kushilevitz, Nathan Linial, Rafail Ostrovsky:
  The Linear-Array Conjecture in Communication Complexity is False. 1-10
  
• Johan Håstad:
  Testing of the Long Code and Hardness for Clique. 11-19
  
• Noga Alon, Yossi Matias, Mario Szegedy:
  The Space Complexity of Approximating the Frequency Moments. 20-29
  
• Shiva Chaudhuri, Jaikumar Radhakrishnan:
  Deterministic Restrictions in Circuit Complexity. 30-36
  

Session 1B

• Joseph Cheriyan, Ramakrishna Thurimella:
  Fast Algorithms for k-Shredders and k-Node Connectivity Augmentation (Extended Abstract). 37-46
  
• András A. Benczúr, David R. Karger:
  Approximating s-t Minimum Cuts in Õ(n²) Time. 47-55
  
• David R. Karger:
  Minimum Cuts in Near-Linear Time. 56-63
  
• Hiroshi Nagamochi, Toshihide Ibaraki:
  Deterministic Õ(nm) Time Edge-Splitting in Undirected Graphs. 64-73
  

Session 2A

• Moni Naor:
  Evaluation May Be Easier Than Generation (Extended Abstract). 74-83
  
• Mitsunori Ogihara:
  The PL Hierarchy Collapses. 84-88
  
• Yehuda Afek, Yishay Mansour, Zvi Ostfeld:
  Convergence Complexity of Optimistic Rate Based Flow Control Algorithms (Extended Abstract). 89-98
  

Session 2B

• Miklós Ajtai:
  Generating Hard Instances of Lattice Problems (Extended Abstract). 99-108
  
• Victor Milenkovic:
  Translational Polygon Containment and Minimal Enclosure using Linear Programming Based Restriction. 109-118
  
• Marshall W. Bern, Amit Sahai:
  Pushing Disks Together - The Continuous-Motion Case. 119-125
  

Session 3A

• Francesco Bergadano, Dario Catalano, Stefano Varricchio:
  Learning Sat-k-DNF Formulas from Membership Queries. 126-130
  
• Nader H. Bshouty:
  Towards the Learnability of DNF Formulae. 131-140
  
• Nicolò Cesa-Bianchi, Eli Dichterman, Paul Fischer, Hans-Ulrich Simon:
  Noise-Tolerant Learning Near the Information-Theoretic Bound. 141-150
  
• Nader H. Bshouty, Sally A. Goldman, H. David Mathias, Subhash Suri, Hisao Tamaki:
  Noise-Tolerant Distribution-Free Learning of General Geometric Concepts. 151-160
  

Session 3B

• Eric Allender, Robert Beals, Mitsunori Ogihara:
  The Complexity of Matrix Rank and Feasible Systems of Linear Equations (Extended Abstract). 161-167
  
• Saugata Basu, Richard Pollack, Marie-Françoise Roy:
  Computing Roadmaps of Semi-Algebraic Sets (Extended Abstract). 168-173
  
• Matthew Clegg, Jeff Edmonds, Russell Impagliazzo:
  Using the Groebner Basis Algorithm to Find Proofs of Unsatisfiability. 174-183
  
• Deepak Kapur, Tushar Saxena:
  Sparsity Considerations in Dixon Resultants. 184-191
  

Session 4A

• Darren Erik Vengroff, Jeffrey Scott Vitter:
  Efficient 3-D Range Searching in External Memory. 192-201
  
• Haim Kaplan, Robert Endre Tarjan:
  Purely Functional Representations of Catenable Sorted Lists. 202-211
  
• Lov K. Grover:
  A Fast Quantum Mechanical Algorithm for Database Search. 212-219
  

Session 4B

• Maria Luisa Bonet, Cynthia A. Phillips, Tandy Warnow, Shibu Yooseph:
  Constructing Evolutionary Trees in the Presence of Polymorphic Characters. 220-229
  
• Martin Farach, Sampath Kannan:
  Efficient Algorithms for Inverting Evolution. 230-236
  

Session 5A

• James Aspnes, Orli Waarts:
  Modular Competitiveness for Distributed Algorithms. 237-246
  
• Michael T. Goodrich:
  Communication-Efficient Parallel Sorting (Preliminary Version). 247-256
  
• Matthew Andrews, Frank Thomson Leighton, Panagiotis Takis Metaxas, Lisa Zhang:
  Automatic Methods for Hiding Latency in High Bandwidth Networks (Extended Abstract). 257-265
  
• Yuan Ma:
  An O(n log n)-Size Fault-Tolerant Sorting Network (Extended Abstract). 266-275
  

Session 5B

• Amnon Ta-Shma:
  On Extracting Randomness From Weak Random Sources (Extended Abstract). 276-285
  
• David Zuckerman:
  Randomness-Optimal Sampling, Extractors, and Constructive Leader Election. 286-295
  
• David Bruce Wilson:
  Generating Random Spanning Trees More Quickly than the Cover Time. 296-303
  
• Tassos Dimitriou, Russell Impagliazzo:
  Towards an Analysis of Local Optimization Algorithms. 304-313
  

Session 6: Knuth Prize Lecture

Session 7A

• Uriel Feige:
  A Threshold of ln n for Approximating Set Cover (Preliminary Version). 314-318
  
• S. Thomas McCormick:
  Fast Algorithms for Parametric Scheduling Come from Extensions to Parametric Maximum Flow. 319-328
  
• Sanjeev Khanna, Rajeev Motwani:
  Towards a Syntactic Characterization of PTAS. 329-337
  
• Philip N. Klein, Hsueh-I Lu:
  Efficient Approximation Algorithms for Semidefinite Programs Arising from MAX CUT and COLORING. 338-347
  

Session 7B

• Andrei Z. Broder, Eli Upfal:
  Dynamic Deflection Routing on Arrays (Preliminary Version). 348-355
  
• Robert Cypher, Friedhelm Meyer auf der Heide, Christian Scheideler, Berthold Vöcking:
  Universal Algorithms for Store-and-Forward and Wormhole Routing. 356-365
  
• Yuval Rabani, Éva Tardos:
  Distributed Packet Switching in Arbitrary Networks. 366-375
  
• Allan Borodin, Jon M. Kleinberg, Prabhakar Raghavan, Madhu Sudan, David P. Williamson:
  Adversarial Queueing Theory. 376-385
  

Session 8A

• Joel Friedman:
  Computing Betti Numbers via Combinatorial Laplacians. 386-391
  
• Bojan Mohar:
  Embedding Graphs in an Arbitrary Surface in Linear Time. 392-397
  
• Tamal K. Dey, Sumanta Guha:
  Algorithms for Manifolds and Simplicial Complexes in Euclidean 3-Space (Preliminary Version). 398-407
  
• Saugata Basu:
  On Bounding the Betti Numbers and Computing the Euler Characteristic of Semi-Algebraic Sets. 408-417
  

Session 8B

• Hans Kellerer, Thomas Tautenhahn, Gerhard J. Woeginger:
  Approximability and Nonapproximability Results for Minimizing Total Flow Time on a Single Machine. 418-426
  
• Howard J. Karloff:
  How Good is the Goemans-Williamson MAX CUT Algorithm? 427-434
  
• Petr Slavík:
  A Tight Analysis of the Greedy Algorithm for Set Cover. 435-441
  
• Avrim Blum, R. Ravi, Santosh Vempala:
  A Constant-factor Approximation Algorithm for the k MST Problem (Extended Abstract). 442-448
  

Session 9A

• Bonnie Berger, Jon M. Kleinberg, Frank Thomson Leighton:
  Reconstructing a Three-Dimensional Model with Arbitrary Errors. 449-458
  
• Michael J. Kearns, Yishay Mansour:
  On the Boosting Ability of Top-Down Decision Tree Learning Algorithms. 459-468
  
• Dana Angluin, Jeffery Westbrook, Wenhong Zhu:
  Robot Navigation with Range Queries. 469-478
  

Session 9B

• Donald Beaver:
  Correlated Pseudorandomness and the Complexity of Private Computations. 479-488
  
• Cynthia Dwork, Jeffrey B. Lotspiech, Moni Naor:
  Digital Signets: Self-Enforcing Protection of Digital Information (Preliminary Version). 489-498
  
• Yair Frankel, Peter Gemmell, Moti Yung:
  Witness-Based Cryptographic Program Checking and Robust Function Sharing. 499-508
  

Session 10A

• Nathan Linial, Ori Sasson:
  Non-Expansive Hashing. 509-518
  
• Baruch Awerbuch, Yossi Azar, Amos Fiat, Frank Thomson Leighton:
  Making Commitments in the Face of Uncertainty: How to Pick a Winner Almost Every Time (Extended Abstract). 519-530
  
• Yair Bartal, Amos Fiat, Stefano Leonardi:
  Lower Bounds for On-line Graph Problems with Application to On-line Circuit and Optical Routing. 531-540
  

Session 10B

• Eyal Kushilevitz, Rafail Ostrovsky, Adi Rosén:
  Characterizing Linear Size Circuits in Terms of Privacy. 541-550
  
• Juraj Hromkovic, Georg Schnitger:
  Nondeterministic Communication with a Limited Number of Advice Bits. 551-560
  
• Ilan Newman, Mario Szegedy:
  Public vs. Private Coin Flips in One Round Communication Games (Extended Abstract). 561-570
  

Session 11A

• Neil Robertson, Daniel P. Sanders, Paul D. Seymour, Robin Thomas:
  Efficiently Four-Coloring Planar Graphs. 571-575
  
• Daniel A. Spielman:
  Faster Isomorphism Testing of Strongly Regular Graphs. 576-584
  
• Alok Aggarwal, Jon M. Kleinberg, David P. Williamson:
  Node-Disjoint Paths on the Mesh and a New Trade-Off in VLSI Layout. 585-594
  

Session 11B

• Xudong Fu:
  Modular Coloring Formulas Are Hard for Cutting Planes Proofs. 595-602
  
• László Babai, Anna Gál, János Kollár, Lajos Rónyai, Tibor Szabó, Avi Wigderson:
  Extremal Bipartite Graphs and Superpolynomial Lower Bounds for Monotone Span Programs. 603-611
  
• Dima Grigoriev, Marek Karpinski, Friedhelm Meyer auf der Heide, Roman Smolensky:
  A Lower Bound for Randomized Algebraic Decision Trees. 612-619
  
• William S. Evans, Nicholas Pippenger:
  Lower Bounds for Noisy Boolean Decision Trees. 620-628
  

Session 12

• Donald Beaver:
  Adaptive Zero Knowledge and Computational Equivocation (Extended Abstract). 629-638
  
• Ran Canetti, Uriel Feige, Oded Goldreich, Moni Naor:
  Adaptively Secure Multi-Party Computation. 639-648
  
• Tatsuaki Okamoto:
  On Relationships between Statistical Zero-Knowledge Proofs. 649-658
  

Errata

• S. Rao Kosaraju, Arthur L. Delcher:
  Large-Scale Assembly of DNA Strings and Space-Efficient Construction of Suffix Trees (Correction). 659