Structural complexity theory: Recent surprises

This publication has 19 references indexed in Scilit:

• Probability one separation of the Boolean hierarchy
  Published by Springer Nature ,2006
• Interactive proof systems
  Proceedings of Symposia in Applied Mathematics, 1989
• Are there interactive protocols for co-NP languages?
  Information Processing Letters, 1988
• Proofs that yield nothing but their validity and a methodology of cryptographic protocol design
  Published by Institute of Electrical and Electronics Engineers (IEEE) ,1986
• With probability one, a random oracle separates PSPACE from the polynomial-time hierarchy
  Published by Association for Computing Machinery (ACM) ,1986
• Private coins versus public coins in interactive proof systems
  Published by Association for Computing Machinery (ACM) ,1986
• Relative to a Random OracleA, ${\bf P}^A \ne {\bf NP}^A \ne \text{co-}{\bf NP}^A $ with Probability 1
  SIAM Journal on Computing, 1981
• Computational Complexity of Probabilistic Turing Machines
  SIAM Journal on Computing, 1977
• On Isomorphisms and Density of $NP$ and Other Complete Sets
  SIAM Journal on Computing, 1977
• Relativizations of the $\mathcal{P} = ?\mathcal{NP}$ Question
  SIAM Journal on Computing, 1975