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