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 BibTeX
Steven Homer, Alan L. Selman: Oracles for Structural Properties: The Isomorphism Problem and Public-Key Cryptography. 3-14 BibTeX
Osamu Watanabe, Shouwen Tang: On Polynomial Time Turing and Many-One Completeness in PSPACE. 15-23 BibTeX
Jie Wang: P-Creative Sets vs. P-Completely Creative Sets. 24-33 BibTeX

Monday Afternoon Session

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

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 BibTeX
Yves Marcoux: Composition is Almost as Good as S-1-1. 77-86 BibTeX
Kenneth W. Regan: Finitary Substructure Languages. 87-96 BibTeX
Jerry L. Trahan, Michael C. Loui, Vijaya Ramachandran: The Power of Parallel Random Access Machines with Augmented Instruction Sets. 97-103 BibTeX
Neil Immerman, Susan Landau: The Complexity of Iterated Multiplication. 104-111 BibTeX

Wednesday Morning Session

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

Wednesday Afternoon Session

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

Thursday Morning Session

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

Thursday Afternoon Session

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