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)

9 ×#algorithm
9 ×#parallel
6 ×#bound
6 ×#performance
4 ×#polynomial
3 ×#geometry
3 ×#random
3 ×#source code
2 ×#approximate
2 ×#branch

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.