default search action
Google
Google Scholar
Semantic Scholar
Internet Archive Scholar
CiteSeerX
ORCID4th SCT 1989: Eugene, Oregon, USA
- Proceedings: Fourth Annual Structure in Complexity Theory Conference, University of Oregon, Eugene, Oregon, USA, June 19-22, 1989. IEEE Computer Society 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
, Avi Wigderson:
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 F. 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: PNP[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
manage site settings
To protect your privacy, all features that rely on external API calls from your browser are turned off by default. You need to opt-in for them to become active. All settings here will be stored as cookies with your web browser. For more information see our F.A.Q.
last updated on 2025-11-07 00:48 CET by the dblp team
all metadata released as open data under CC0 1.0 license
see also: Terms of Use | Privacy Policy | Imprint
dblp was originally created in 1993 at:
since 2018, dblp has been operated and maintained by:
the dblp computer science bibliography is funded and supported by:
