28. STOC 1996: Philadephia, Pennsylvania, USA

Proceedings of the Twenty-Eighth Annual ACM Symposium on the Theory of Computing, Philadelphia, Pennsylvania, USA, May 22-24, 1996. ACM, 1996, ISBN 0-89791-785-5

Session 1A

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

Session 1B

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

Session 2A

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

Session 2B

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

Session 3A

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

Session 3B

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

Session 4A

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

Session 4B

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

Session 5A

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

Session 5B

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

Session 6: Knuth Prize Lecture

Session 7A

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

Session 7B

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

Session 8A

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

Session 8B

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

Session 9A

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

Session 9B

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

Session 10A

Nathan Linial, Ori Sasson:
Non-Expansive Hashing. 509-518
Electronic Edition (ACM DL) BibTeX
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
Electronic Edition (ACM DL) BibTeX
Yair Bartal, Amos Fiat, Stefano Leonardi:
Lower Bounds for On-line Graph Problems with Application to On-line Circuit and Optical Routing. 531-540
Electronic Edition (ACM DL) BibTeX

Session 10B

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

Session 11A

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

Session 11B

Xudong Fu:
Modular Coloring Formulas Are Hard for Cutting Planes Proofs. 595-602
Electronic Edition (ACM DL) BibTeX
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
Electronic Edition (ACM DL) BibTeX
Dima Grigoriev, Marek Karpinski, Friedhelm Meyer auf der Heide, Roman Smolensky:
A Lower Bound for Randomized Algebraic Decision Trees. 612-619
Electronic Edition (ACM DL) BibTeX
William S. Evans, Nicholas Pippenger:
Lower Bounds for Noisy Boolean Decision Trees. 620-628
Electronic Edition (ACM DL) BibTeX

Session 12

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

Errata

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