1. CoCo 1986:
Berkeley,
California,
USA
Alan L. Selman (Ed.):
Structure in Complexity Theory, Proceedings of the Conference hold at the University of California, Berkeley, California, June 2-5, 1986.
Lecture Notes in Computer Science 223 Springer 1986, ISBN 3-540-16486-3 
- Eric Allender:
The Complexity of Sparse Sets in P.
1-11
- Eric Allender:
Isomorphisms and 1-L Reductions.
12-22
- Klaus Ambos-Spies:
Randomness, Relativizations, and Polynomial Reducibilities.
23-34
- José L. Balcázar, Josep Díaz, Joaquim Gabarró:
On Non- uniform Polynomial Space.
35-50
- Ravi B. Boppana, J. C. Lagarias:
One- Way Functions and Circuit Complexity.
51-65
- Jonathan F. Buss:
Relativized Alternation.
66-76
- Samuel R. Buss:
The Polynomial Hierarchy and Intuitionistic Bounded Arithmetic.
77-103
- Jin-yi Cai:
With Probability One, A Random Oracle Separates PSPACE from the Polynomial- Time Hierarchy.
104-104
- Jin-yi Cai, Lane A. Hemachandra:
The Boolean Hierarchy: Hardware over NP.
105-124
- Peter Clote, Gaisi Takeuti:
Exponential Time and Bounded Arithmetic.
125-143
- Anne Condon, Richard E. Ladner:
Probabilistic Game Automata.
144-162
- Martin Dietzfelbinger, Wolfgang Maass:
two Lower Bound Arguments with "Inaccessible" Numbers.
163-183
- Dung T. Huynh:
Resource- Bounded Kolmogorov Complexity of Hard Languages.
184-195
- Ker-I Ko, Timothy J. Long, Ding-Zhu Du:
A Note on One- Way Functions and Polynomial Time Isomorphisms.
196-196
- Ker-I Ko, Pekka Orponen, Uwe Schöning, Osamu Watanabe:
What Is a Hard Instance of a Computational Problem?.
197-217
- Mark W. Krentel:
The Complexity of Optimization Problems.
217-217
- Ming Li, Luc Longpré, Paul M. B. Vitányi:
The Power of the Queue.
218-233
- James F. Lynch:
A Depth- Size Tradeoff for Boolean Circuits with Unbounded Fan- In.
234-248
- Wolfgang Maass, Georg Schnitger:
An Optimal Lower Bound for Turing Machines with One Work Tape and a Two- way Input Tape.
249-264
- Ken McAloon:
Separation Results for Bounded Alternation.
265-271
- Ian Parberry, Georg Schnitger:
Parallel Computation with Threshold Functions.
272-290
- Kenneth W. Regan:
The Topology of Provability in Complexity Theory.
291-310
- David A. Russo:
Optimal Approximations of Complete Sets.
311-324
- Michael Sipser:
Expanders, Randomness, or Time versus Space.
325-329
- Leen Torenvliet, Peter van Emde Boas:
Diagonalisation methods in a polynomial setting.
330-346
- Carol Tretkoff:
Bounded Oracles and Complexity Classes Inside Linear Space.
347-361
- Christopher B. Wilson:
Parallel Computation and the NC Hierarchy Relativized.
362-382
- Stathis Zachos:
Probabilistic Quantifiers, Adversaries, and Complexity Classes: An Overview.
383-400
Last update Tue May 22 04:49:08 2012
CET by the DBLP Team — 
Data released under the ODC-BY 1.0 license — See also our legal information page
