## Juris Hartmanis

*Proceedings of the 18th Annual ACM Symposium on Theory of Computing*

STOC, 1986.

@proceedings{STOC-1986, address = "Berkeley, California, USA", editor = "Juris Hartmanis", isbn = "0-89791-193-8", publisher = "{ACM}", title = "{Proceedings of the 18th Annual ACM Symposium on Theory of Computing}", year = 1986, }

### Contents (47 items)

- STOC-1986-Barrington #bound #branch #source code
- Bounded-Width Polynomial-Size Branching Programs Recognize Exactly Those Languages in NC¹ (DAMB), pp. 1–5.
- STOC-1986-Hastad #bound
- Almost Optimal Lower Bounds for Small Depth Circuits (JH), pp. 6–20.
- STOC-1986-Cai #polynomial #probability #random
- With Probability One, A Random Oracle Separates PSPACE from the Polynomial-Time Hierarchy (JyC), pp. 21–29.
- STOC-1986-AjtaiBHKPRST #bound #branch #source code
- Two lower bounds for branching programs (MA, LB, PH, JK, PP, VR, ES, GT), pp. 30–38.
- STOC-1986-GalilKS #graph #nondeterminism #on the #simulation #turing machine
- On Nontrivial Separators for k-Page Graphs and Simulations by Nondeterministic One-Tape Turing Machines (ZG, RK, ES), pp. 39–49.
- STOC-1986-Broder #approximate #how #random
- How hard is to marry at random? (On the approximation of the permanent) (AZB), pp. 50–58.
- STOC-1986-GoldwasserS #interactive #proving
- Private Coins versus Public Coins in Interactive Proof Systems (SG, MS), pp. 59–68.
- STOC-1986-Krentel #complexity #optimisation #problem
- The Complexity of Optimization Problems (MWK), pp. 69–76.
- STOC-1986-CoffmanL #algorithm #performance
- A Provably Efficient Algorithm for Dynamic Storage Allocation (EGCJ, FTL), pp. 77–90.
- STOC-1986-LeightonS #algorithm #analysis #bound #grid
- Tight Bounds for Minimax Grid Matching, With Applications to the Average Case Analysis of Algorithms (FTL, PWS), pp. 91–103.
- STOC-1986-Yannakakis #graph
- Four Pages are Necessary and Sufficient for Planar Graphs (MY), pp. 104–108.
- STOC-1986-DriscollSST #data type #persistent
- Making Data Structures Persistent (JRD, NS, DDS, RET), pp. 109–121.
- STOC-1986-SleatorTT #distance #geometry
- Rotation Distance, Triangulations, and Hyperbolic Geometry (DDS, RET, WPT), pp. 122–135.
- STOC-1986-GoldbergT #approach #problem
- A New Approach to the Maximum Flow Problem (AVG, RET), pp. 136–146.
- STOC-1986-KapoorV #algorithm #multi #performance #polynomial #programming
- Fast Algorithms for Convex Quadratic Programming and Multicommodity Flows (SK, PMV), pp. 147–159.
- STOC-1986-KarlinU #implementation #memory management #parallel #performance
- Parallel Hashing-An Efficient Implementation of Shared Memory (ARK, EU), pp. 160–168.
- STOC-1986-Beame #parallel #power of
- Limits on the Power of Concurrent-Write Parallel Machines (PB), pp. 169–176.
- STOC-1986-LiY #bound #parallel
- New Lower Bounds for Parallel Computation (ML, YY), pp. 177–187.
- STOC-1986-AjtaiKSS #parallel
- Deterministic Selection in O(log log N) Parallel Time (MA, JK, WLS, ES), pp. 188–195.
- STOC-1986-LuekerMR #difference #linear #programming
- Linear Programming with Two Variables per Inequality in Poly-Log Time (GSL, NM, VR), pp. 196–205.
- STOC-1986-ColeV #algorithm #design #metaprogramming #parallel
- Deterministic coin tossing and accelerating cascades: micro and macro techniques for designing parallel algorithms (RC, UV), pp. 206–219.
- STOC-1986-LandauV #algorithm #approximate #parallel #performance #string
- Introducing Efficient Parallelism into Approximate String Matching and a New Serial Algorithm (GML, UV), pp. 220–230.
- STOC-1986-Kosaraju #evaluation #parallel
- Parallel Evaluation of Division-Free Arithmetic Expressions (SRK), pp. 231–239.
- STOC-1986-LubotzkyPS
- Explicit Expanders and the Ramanujan Conjectures (AL, RP, PS), pp. 240–246.
- STOC-1986-FeldmanFP #network
- Non-Blocking Networks (PF, JF, NP), pp. 247–254.
- STOC-1986-SchnorrS #algorithm #sorting
- An Optimal Sorting Algorithm for Mesh Connected Computers (CPS, AS), pp. 255–263.
- STOC-1986-KosarajuA #array #simulation
- Optimal Simulations between Mesh-Connected Arrays of Processors (SRK, MJA), pp. 264–272.
- STOC-1986-BlumerEHW #concept #geometry
- Classifying Learnable Geometric Concepts with the Vapnik-Chervonenkis Dimension (AB, AE, DH, MKW), pp. 273–282.
- STOC-1986-CourcoubetisVW #concurrent #reasoning #source code
- Reasoning about Fair Concurrent Programs (CC, MYV, PW), pp. 283–294.
- STOC-1986-KoLD #morphism #polynomial
- A Note on One-Way Functions and Polynomial-Time Isomorphisms (KIK, TJL, DZD), pp. 295–303.
- STOC-1986-HalpernV #complexity #reasoning
- The Complexity of Reasoning about Knowledge and Time: Extended Abstract (JYH, MYV), pp. 304–315.
- STOC-1986-GoldwasserK
- Almost All Primes Can Be Quickly Certified (SG, JK), pp. 316–329.
- STOC-1986-Kaltofen
- Uniform Closure Properties of P-Computable Functions (EK), pp. 330–337.
- STOC-1986-Mulmuley #algorithm #matrix #parallel #performance #rank
- A Fast Parallel Algorithm to Compute the Rank of a Matrix over an Arbitrary Field (KM), pp. 338–339.
- STOC-1986-Ben-OrFKT #algorithm #parallel #performance #polynomial
- A Fast Parallel Algorithm for Determining All Roots of a Polynomial with Real Roots (MBO, EF, DK, PT), pp. 340–349.
- STOC-1986-AdlemanL #finite
- Finding Irreducible Polynomials over Finite Fields (LMA, HWLJ), pp. 350–355.
- STOC-1986-LubyR #composition #encryption #generative #permutation #pseudo
- Pseudo-random Permutation Generators and Cryptographic Composition (ML, CR), pp. 356–363.
- STOC-1986-Cleve #security
- Limits on the Security of Coin Flips when Half the Processors Are Faulty (RC), pp. 364–369.
- STOC-1986-DworkPPU #bound #fault tolerance #network
- Fault Tolerance in Networks of Bounded Degree (CD, DP, NP, EU), pp. 370–379.
- STOC-1986-TarjanW #algorithm #linear
- A Linear-Time Algorithm for Triangulating Simple Polygons (RET, CJVW), pp. 380–388.
- STOC-1986-EdelsbrunnerG
- Topologically Sweeping an Arrangement (HE, LJG), pp. 389–403.
- STOC-1986-Seidel
- Constructing Higher-Dimensional Convex Hulls at Logarithmic Cost per Face (RS), pp. 404–413.
- STOC-1986-Clarkson #geometry #random
- Further Applications of Random Sampling to Computational Geometry (KLC), pp. 414–423.
- STOC-1986-DobkinEY
- Probing Convex Polytopes (DPD, HE, CKY), pp. 424–432.
- STOC-1986-Bern #probability
- Two Probabilistic Results on Rectilinear Steiner Trees (MWB), pp. 433–441.
- STOC-1986-BaranyF
- Computing the Volume Is Difficult (IB, ZF), pp. 442–447.
- STOC-1986-Siegel #aspect-oriented #data flow
- Aspects of Information Flow in VLSI Circuits (AS), pp. 448–459.

9 ×#algorithm

9 ×#parallel

6 ×#bound

6 ×#performance

4 ×#polynomial

3 ×#geometry

3 ×#random

3 ×#source code

2 ×#approximate

2 ×#branch

9 ×#parallel

6 ×#bound

6 ×#performance

4 ×#polynomial

3 ×#geometry

3 ×#random

3 ×#source code

2 ×#approximate

2 ×#branch