default search action
18th STOC 1986: Berkeley, California, USA
- Juris Hartmanis:
Proceedings of the 18th Annual ACM Symposium on Theory of Computing, May 28-30, 1986, Berkeley, California, USA. ACM 1986, ISBN 0-89791-193-8 - David A. Mix Barrington:
Bounded-Width Polynomial-Size Branching Programs Recognize Exactly Those Languages in NC¹. 1-5 - Johan Håstad:
Almost Optimal Lower Bounds for Small Depth Circuits. 6-20 - Jin-yi Cai:
With Probability One, A Random Oracle Separates PSPACE from the Polynomial-Time Hierarchy. 21-29 - Miklós Ajtai, László Babai, Péter Hajnal, János Komlós, Pavel Pudlák, Vojtech Rödl, Endre Szemerédi, György Turán:
Two lower bounds for branching programs. 30-38 - Zvi Galil, Ravi Kannan, Endre Szemerédi:
On Nontrivial Separators for k-Page Graphs and Simulations by Nondeterministic One-Tape Turing Machines. 39-49 - Andrei Z. Broder:
How hard is to marry at random? (On the approximation of the permanent). 50-58 - Shafi Goldwasser, Michael Sipser:
Private Coins versus Public Coins in Interactive Proof Systems. 59-68 - Mark W. Krentel:
The Complexity of Optimization Problems. 69-76 - Edward G. Coffman Jr., Frank Thomson Leighton:
A Provably Efficient Algorithm for Dynamic Storage Allocation. 77-90 - Frank Thomson Leighton, Peter W. Shor:
Tight Bounds for Minimax Grid Matching, With Applications to the Average Case Analysis of Algorithms. 91-103 - Mihalis Yannakakis:
Four Pages are Necessary and Sufficient for Planar Graphs (Extended Abstract). 104-108 - James R. Driscoll, Neil Sarnak, Daniel Dominic Sleator, Robert Endre Tarjan:
Making Data Structures Persistent. 109-121 - Daniel Dominic Sleator, Robert Endre Tarjan, William P. Thurston:
Rotation Distance, Triangulations, and Hyperbolic Geometry. 122-135 - Andrew V. Goldberg, Robert Endre Tarjan:
A New Approach to the Maximum Flow Problem. 136-146 - Sanjiv Kapoor, Pravin M. Vaidya:
Fast Algorithms for Convex Quadratic Programming and Multicommodity Flows. 147-159 - Anna R. Karlin, Eli Upfal:
Parallel Hashing-An Efficient Implementation of Shared Memory (Preliminary Version). 160-168 - Paul Beame
:
Limits on the Power of Concurrent-Write Parallel Machines. 169-176 - Ming Li, Yaacov Yesha:
New Lower Bounds for Parallel Computation. 177-187 - Miklós Ajtai, János Komlós, William L. Steiger, Endre Szemerédi:
Deterministic Selection in O(log log N) Parallel Time. 188-195 - George S. Lueker, Nimrod Megiddo, Vijaya Ramachandran:
Linear Programming with Two Variables per Inequality in Poly-Log Time (Preliminary Version). 196-205 - Richard Cole, Uzi Vishkin:
Deterministic coin tossing and accelerating cascades: micro and macro techniques for designing parallel algorithms. 206-219 - Gad M. Landau, Uzi Vishkin:
Introducing Efficient Parallelism into Approximate String Matching and a New Serial Algorithm. 220-230 - S. Rao Kosaraju:
Parallel Evaluation of Division-Free Arithmetic Expressions. 231-239 - Alexander Lubotzky
Explicit Expanders and the Ramanujan Conjectures. 240-246 - Paul Feldman, Joel Friedman, Nicholas Pippenger:
Non-Blocking Networks (Preliminary Version). 247-254 - Claus-Peter Schnorr, Adi Shamir:
An Optimal Sorting Algorithm for Mesh Connected Computers. 255-263 - S. Rao Kosaraju, Mikhail J. Atallah:
Optimal Simulations between Mesh-Connected Arrays of Processors (Preliminary Version). 264-272 - Anselm Blumer, Andrzej Ehrenfeucht, David Haussler, Manfred K. Warmuth:
Classifying Learnable Geometric Concepts with the Vapnik-Chervonenkis Dimension (Extended Abstract). 273-282 - Costas Courcoubetis, Moshe Y. Vardi, Pierre Wolper:
Reasoning about Fair Concurrent Programs. 283-294 - Ker-I Ko, Timothy J. Long, Ding-Zhu Du:
A Note on One-Way Functions and Polynomial-Time Isomorphisms (Extended Abstract). 295-303 - Joseph Y. Halpern, Moshe Y. Vardi:
The Complexity of Reasoning about Knowledge and Time: Extended Abstract. 304-315 - Shafi Goldwasser, Joe Kilian:
Almost All Primes Can Be Quickly Certified. 316-329 - Erich L. Kaltofen:
Uniform Closure Properties of P-Computable Functions. 330-337 - Ketan Mulmuley:
A Fast Parallel Algorithm to Compute the Rank of a Matrix over an Arbitrary Field. 338-339 - Michael Ben-Or, Ephraim Feig, Dexter Kozen, Prasoon Tiwari:
A Fast Parallel Algorithm for Determining All Roots of a Polynomial with Real Roots. 340-349 - Leonard M. Adleman, Hendrik W. Lenstra Jr.:
Finding Irreducible Polynomials over Finite Fields. 350-355 - Michael Luby, Charles Rackoff:
Pseudo-random Permutation Generators and Cryptographic Composition. 356-363 - Richard Cleve:
Limits on the Security of Coin Flips when Half the Processors Are Faulty (Extended Abstract). 364-369 - Cynthia Dwork, David Peleg, Nicholas Pippenger, Eli Upfal:
Fault Tolerance in Networks of Bounded Degree (Preliminary Version). 370-379 - Robert Endre Tarjan, Christopher J. Van Wyk:
A Linear-Time Algorithm for Triangulating Simple Polygons. 380-388 - Herbert Edelsbrunner, Leonidas J. Guibas:
Topologically Sweeping an Arrangement. 389-403 - Raimund Seidel:
Constructing Higher-Dimensional Convex Hulls at Logarithmic Cost per Face. 404-413 - Kenneth L. Clarkson:
Further Applications of Random Sampling to Computational Geometry. 414-423 - David P. Dobkin, Herbert Edelsbrunner, Chee-Keng Yap:
Probing Convex Polytopes. 424-432 - Marshall W. Bern:
Two Probabilistic Results on Rectilinear Steiner Trees. 433-441 - Imre Bárány, Zoltán Füredi:
Computing the Volume Is Difficult. 442-447 - Alan Siegel:
Aspects of Information Flow in VLSI Circuits (Extended Abstract). 448-459
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-12-19 22:02 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: