4. CoCo 1989: Eugene, Oregon, USA

Proceedings: Fourth Annual Structure in Complexity Theory Conference, June 19-22, 1989, University of Oregon, Eugene, Oregon, USA. IEEE Computer Society Press, 1989, ISBN 0-8186-1958-9

Monday Morning Session

Stuart A. Kurtz, Stephen R. Mahaney, James S. Royer: The Isomorphism Conjecture Fails Relative to a Random Oracle (abstract). 2
Steven Homer, Alan L. Selman: Oracles for Structural Properties: The Isomorphism Problem and Public-Key Cryptography. 3-14
Osamu Watanabe, Shouwen Tang: On Polynomial Time Turing and Many-One Completeness in PSPACE. 15-23
Jie Wang: P-Creative Sets vs. P-Completely Creative Sets. 24-33

Monday Afternoon Session

Shai Ben-David, Benny Chor, Oded Goldreich, Michael Luby: On the Theory of Average Case Complexity (abstract). 36
Jack H. Lutz: Almost Everywhere High Nonuniform Complexity. 37-53
Noam Nisan: Hardness vs. Randomness - A Survey (abstract). 54
Peter Clote: Boolean Functions, Invariance Groups and Parallel Complexity. 55-66

Tuesday Morning Session

Richard A. Shore, Theodore A. Slaman: The P-T-Degrees of the Recursive Sets: Lattice Embeddings, Extension of Embeddings and the Two Quantifier Theory. 68-76
Yves Marcoux: Composition is Almost as Good as S-1-1. 77-86
Kenneth W. Regan: Finitary Substructure Languages. 87-96
Jerry L. Trahan, Michael C. Loui, Vijaya Ramachandran: The Power of Parallel Random Access Machines with Augmented Instruction Sets. 97-103
Neil Immerman, Susan Landau: The Complexity of Iterated Multiplication. 104-111

Wednesday Morning Session

Ernst W. Mayr, Ashok Subramanian: The Complexity of Circuit Value and Network Stability. 114-123
Christopher B. Wilson: Decomposing NC and AC. 124-131
Mark W. Krentel: On Finding Locally Optimal Solutions. 132-137
Jin-yi Cai, Juris Hartmanis: The Complexity Of The Real Line Is A Fractal. 138-146

Wednesday Afternoon Session

Tak Wah Lam, Walter L. Ruzzo: Results on Communication Complexity Classes. 148-157
Uriel Feige, Adi Shamir: Multi-Oracle Interactive Protocols with Space Bounded Verifiers. 158-164
Ming Li, Paul M. B. Vitányi: Inductive Reasoning and Komogorov Complexity. 165-185
Eric Allender: The Generalized Kolmogorov Complexity of Sets. 186-194

Thursday Morning Session

Rodney G. Downey, Steven Homer, William I. Gasarch, Michael Moses: On Honest Polynomial Reductions, Relativizations, and P=NP. 196-207
Johannes Köbler, Uwe Schöning, Seinosuke Toda, Jacobo Torán: Turing Machines with few Accepting Computations and low Sets for PP. 208-215
Richard Beigel: On the Relativized Power of Additional Accepting Paths. 216-224
Richard Beigel, Lane A. Hemachandra, Gerd Wechsung: On the Power of Probabilistic Polynomial Time: P^NP[log] subseteq PP. 225-227

Thursday Afternoon Session

Leonard Pitt, Manfred K. Warmuth: The Minimum Consistent DFA Problem Cannot be Approximated within any Polynomial (abstract). 230
Wolfgang Maass, Theodore A. Slaman: The Complexity Types of Computable Sets. 231-239
Matthias Krause, Christoph Meinel, Stephan Waack: Seperating Complexity Classes Related to Certain Input Oblivious Logarithmic Space-Bounded Turing Machines. 240-249
Richard Chang: On the Structure of Bounded Queries to Arbitrary NP Sets. 250-258
José L. Balcázar: Nondeterministic Witnesses and Nonuniform Advice. 259-269