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