default search action
Google
Google Scholar
Semantic Scholar
Internet Archive Scholar
CiteSeerX
ORCID28th STOC 1996: Philadephia, Pennsylvania, USA
- Gary L. Miller:
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 - 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 Õ(n2) 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 J. 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 S. 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 R. 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
manage site settings
To protect your privacy, all features that rely on external API calls from your browser are turned off by default. You need to opt-in for them to become active. All settings here will be stored as cookies with your web browser. For more information see our F.A.Q.
last updated on 2024-11-15 19:20 CET by the dblp team
all metadata released as open data under CC0 1.0 license
see also: Terms of Use | Privacy Policy | Imprint
dblp was originally created in 1993 at:
since 2018, dblp has been operated and maintained by:
the dblp computer science bibliography is funded and supported by:
