An Oracle Separating \oplus P from PP^PH

No abstract is available for this paper.

• Publication year

  1991

• Venue

  Information Processing Letters

• Publication date

  1991-02-01

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1016/0020-0190(91)90035-G
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Relativized Counting Classes: Relations among Thresholds, Parity, and Mods

  1991cited by this paper
• On the computational power of PP and (+)P

  1989cited by this paper
• Relativized polynomial time hierarchies having exactly K levels

  1988cited by this paper
• Threshold circuits of bounded depth

  1987cited by this paper
• Computational limitations of small-depth circuits

  1987cited by this paper
• With probability one, a random oracle separates PSPACE from the polynomial-time hierarchy

  1986cited by this paper
• Parallel Computation with Threshold Functions

  1986cited by this paper
• Relative to a Random Oracle A, PA != NPA != co-NPA with Probability 1

  1981cited by this paper

• A complex-number Fourier technique for lower bounds on the Mod-m degree

  2000cites this paper
• Exponential Sums and Circuits with a Single Threshold Gate and Mod-Gates

  1999cites this paper
• On lower bounds for circuits and selection

  1999cites this paper
• A Lower Bound for Perceptrons and an Oracle Separation of the PPPH Hierarchy

  1998cites this paper
• Relating Polynomial Time to Constant Depth

  1998cites this paper
• Immunity and simplicity for exact counting and other counting classes

  1998influential citation
• Upper and lower bounds for some depth-3 circuit classes

  1997cites this paper
• A lower bound for perceptrons and an oracle separation of the PP/sup PH/ hierarchy

  1997cites this paper
• On the Power of a Threshold Gate at the Top

  1997cites this paper
• On the correlation of symmetric functions

  1996cites this paper
• A lower bound for monotone perceptrons

  1995cites this paper
• Lower Bounds for Depth-Three Circuits With Equals and Mod-Gates

  1995cites this paper
• Worlds to die for

  1995cites this paper
• Computing Symmetric Functions with AND/OR Circuits and a Single MAJORITY Gate

  1993cites this paper
• PP is closed under intersection

  1991cites this paper