An oracle separating ⊕P from PP^PH

Frederic Green, Worcester State University

Abstract

The existence of an oracle A such that ⊕PA is not contained in PPPHA is proved. This separation follows in a straightforward manner from a circuit complexity result, which is also proved here: to compute the parity of n inputs, any constant depth circuit consisting of a single threshold gate on top of ANDs and ORs requires exponential size in n.