Structure in Complexity Theory: Proceedings of the Conference held at the University of California, Berkeley, California, June 2–5, 1986

The complexity of sparse sets in P....Pages 1-11
Isomorphisms and 1-L reductions....Pages 12-22
Randomness, relativizations, and polynomial reducibilities....Pages 23-34
On non-uniform polynomial space....Pages 35-50
One-way functions and circuit complexity....Pages 51-65
Relativized alternation....Pages 66-76
The polynomial hierarchy and intuitionistic Bounded Arithmetic....Pages 77-103
With probability one, a random oracle separates PSPACE from the polynomial-time hierarchy....Pages 104-104
The boolean hierarchy: Hardware over NP....Pages 105-124
Exponential time and bounded arithmetic....Pages 125-143
Probabilistic game automata....Pages 144-162
Two lower bound arguments with "inaccessible" numbers....Pages 163-183
Resource-bounded Kolmogorov complexity of hard languages....Pages 184-195
A note on one-way functions and polynomial time isomorphisms....Pages 196-196
What is a hard instance of a computational problem?....Pages 197-217
The complexity of optimization problems....Pages 218-218
The power of the queue....Pages 219-233
A depth-size tradeoff for boolean circuits with unbounded fan-in....Pages 234-248
An optimal lower bound for turing machines with one work tape and a two-way input tape....Pages 249-264
Separation results for bounded alternation....Pages 265-271
Parallel computation with threshold functions....Pages 272-290
The topology of provability in complexity theory....Pages 291-310
Optimal approximations of complete sets....Pages 311-324
Expanders, randomness, or time versus space....Pages 325-329
Diagonalisation methods in a polynomial setting....Pages 330-346
Bounded oracles and complexity classes inside linear space....Pages 347-361
Parallel computation and the NC hierarchy relativized....Pages 362-382
Probabilistic quantifiers, adversaries, and complexity classes : An overview....Pages 383-400