18. STOC 1986
Proceedings of the 18th Annual ACM Symposium on Theory of Computing, May 28-30, 1986, Berkeley, California, USA. ACM 1986
- 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, R. Phillips, P. Sarnak:
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 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
Copyright © Tue Nov 10 00:17:38 2009
by Michael Ley (ley@uni-trier.de)
