default search action
19th STOC 1987: New York, New York, USA
- Alfred V. Aho:
Proceedings of the 19th Annual ACM Symposium on Theory of Computing, 1987, New York, New York, USA. ACM 1987, ISBN 0-89791-221-7 - Don Coppersmith, Shmuel Winograd:
Matrix Multiplication via Arithmetic Progressions. 1-6 - Andrew V. Goldberg, Robert Endre Tarjan:
Solving Minimum-Cost Flow Problems by Successive Approximation. 7-18 - Greg N. Frederickson:
A New Approach to All Pairs Shortest Paths in Planar Graphs (Extended Abstract). 19-28 - Pravin M. Vaidya:
An Algorithm for Linear Programming which Requires O(((m+n)n^2 + (m+n)^1.5 n)L) Arithmetic Operations. 29-38 - Alok Aggarwal, Leonidas J. Guibas, James B. Saxe, Peter W. Shor:
A Linear Time Algorithm for Computing the Voronoi Diagram of a Convex Polygon. 39-45 - Kazuo Iwano, Kenneth Steiglitz:
Testing for Cycles in Infinite Graphs with Periodic Structure (Extended Abstract). 46-55 - Kenneth L. Clarkson:
Approximation Algorithms for Shortest Path Motion Planning (Extended Abstract). 56-65 - Bernard Chazelle, Herbert Edelsbrunner, Leonidas J. Guibas:
The Complexity of Cutting Convex Polytopes. 66-76 - Roman Smolensky:
Algebraic Methods in the Theory of Lower Bounds for Boolean Circuit Complexity. 77-82 - Paul Beame
, Johan Håstad:
Optimal Bounds for Decision Problems on the CRCW PRAM. 83-93 - Wolfgang Maass, Georg Schnitger, Endre Szemerédi:
Two Tapes Are Better than One for Off-Line Turing Machines. 94-100 - David A. Mix Barrington, Denis Thérien:
Finite Monoids and the Fine Structure of NC¹. 101-109 - Lane A. Hemachandra
The Strong Exponential Hierarchy Collapses. 110-122 - Samuel R. Buss:
The Boolean Formula Value Problem Is in ALOGTIME. 123-131 - Miklós Ajtai, János Komlós, Endre Szemerédi:
Deterministic Simulation in LOGSPACE. 132-140 - H. Venkateswaran:
Properties that Characterize LOGCFL. 141-150 - Eric Allender:
Some Consequences of the Existence of Pseudorandom Generators. 151-159 - Umesh V. Vazirani:
Efficiency Considerations in Using Semi-random Sources (Extended Abstract). 160-168 - David Lichtenstein, Nathan Linial, Michael E. Saks:
Imperfect Random Sources and Discrete Controlled Processes. 169-177 - Martin Fürer:
The Power of Randomness for Communication Complexity (Preliminary Version). 178-181 - Oded Goldreich:
Towards a Theory of Software Protection and Simulation by Oblivious RAMs. 182-194 - Martín Abadi, Joan Feigenbaum, Joe Kilian:
On Hiding Information from an Oracle (Extended Abstract). 195-203 - Lance Fortnow:
The Complexity of Perfect Zero-Knowledge (Extended Abstract). 204-209 - Uriel Feige, Amos Fiat, Adi Shamir:
Zero Knowledge Proofs of Identity. 210-217 - Oded Goldreich, Silvio Micali, Avi Wigderson:
How to Play any Mental Game or A Completeness Theorem for Protocols with Honest Majority. 218-229 - Baruch Awerbuch:
Optimal Distributed Algorithms for Minimum Weight Spanning Tree, Counting, Leader Election and Related Problems (Detailed Summary). 230-240 - Johan Håstad, Frank Thomson Leighton, Brian Rogoff:
Analysis of Backoff Protocols for Multiple Access Channels (Extended Abstract). 241-253 - Gary L. Miller, Shang-Hua Teng:
Dynamic Parallel Complexity of Computational Circuits. 254-263 - David Peleg, Eli Upfal:
Constructing Disjoint Paths on Expander Graphs (Extended Abstract). 264-273 - Johan Håstad, Frank Thomson Leighton, Mark Newman:
Reconfiguring a Hypercube in the Presence of Faults (Extended Abstract). 274-284 - Michael J. Kearns, Ming Li, Leonard Pitt, Leslie G. Valiant:
On the Learnability of Boolean Formulae. 285-295 - B. K. Natarajan:
On Learning Boolean Functions. 296-304 - Alok Aggarwal, Bowen Alpern, Ashok K. Chandra, Marc Snir:
A Model for Hierarchical Memory. 305-314 - Andrew V. Goldberg, Serge A. Plotkin, Gregory E. Shannon:
Parallel Symmetry-Breaking in Sparse Graphs. 315-324 - Alok Aggarwal, Richard J. Anderson:
A Random NC Algorithm for Depth First Search. 325-334 - Gary L. Miller, Vijaya Ramachandran:
A New Graph Triconnectivity Algorithm and Its Parallelization. 335-344 - Ketan Mulmuley, Umesh V. Vazirani, Vijay V. Vazirani:
Matching Is as Easy as Matrix Inversion. 345-354 - Joseph Naor, Moni Naor, Alejandro A. Schäffer:
Fast Parallel Algorithms for Chordal Graphs (Extended Abstract). 355-364 - Paul F. Dietz, Daniel Dominic Sleator:
Two Algorithms for Maintaining Order in a List. 365-372 - Allan Borodin, Nathan Linial, Michael E. Saks:
An Optimal Online Algorithm for Metrical Task Systems. 373-382 - J. Ian Munro:
Searching a Two Key Table Under a Single Key. 383-387 - Lenwood S. Heath, Sorin Istrail:
The Pagenumber of Genus g Graphs is O(g). 388-397 - Lajos Rónyai:
Simple Algebras Are Difficult. 398-408 - László Babai
Permutation Groups in NC. 409-420 - Saharon Shelah, Joel Spencer:
Threshold Spectra for Random Graphs. 421-424 - Phokion G. Kolaitis, Moshe Y. Vardi:
The Decision Problem for the Probabilities of Higher-Order Properties. 425-435 - Gianfranco Bilardi, Franco P. Preparata:
Size-Time Complexity of Boolean Networks for Prefix Computations. 436-442 - Erich L. Kaltofen
Single-Factor Hensel Lifting and its Application to the Straight-Line Complexity of Certain Polynomials. 443-452 - Eric Bach:
Realistic Analysis of Some Randomized Algorithms. 453-461 - Leonard M. Adleman, Ming-Deh A. Huang:
Recognizing Primes in Random Polynomial Time. 462-469
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-23 19:18 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: