18. STOC 1986: Berkeley, California, USA

• 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, Ralph Phillips, Peter 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
  

Last update Fri May 17 16:19:38 2013 CET by the DBLP Team — Data released under the ODC-BY 1.0 license — See also our legal information page