Stop the war!Остановите войну!
for scientists:
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
a service of 
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-05-31 18:53 CEST 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:
