Lower bounds for constant-depth circuits in the presence of help bits

This publication has 11 references indexed in Scilit:

• The Boolean Hierarchy II: Applications
  SIAM Journal on Computing, 1989
• With probability one, a random oracle separates PSPACE from the polynomial-time hierarchy
  Journal of Computer and System Sciences, 1989
• The Boolean Hierarchy I: Structural Properties
  SIAM Journal on Computing, 1988
• Polynomial terse sets
  Information and Computation, 1988
• The polynomial time hierarchy collapses if the Boolean hierarchy collapses
  Published by Institute of Electrical and Electronics Engineers (IEEE) ,1988
• Lower bounds on the size of bounded depth circuits over a complete basis with logical addition
  Mathematical Notes, 1987
• Parity, circuits, and the polynomial-time hierarchy
  Theory of Computing Systems, 1984
• ∑11-Formulae on finite structures
  Annals of Pure and Applied Logic, 1983
• 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
• The polynomial-time hierarchy
  Theoretical Computer Science, 1976