Green [1] showed that $PP^{PH}$ is properly contained in $PSPACE$ relative to some oracle. Around the same time, in the famous "voting polynomials" paper [2], it was shown that $PP$ is properly contained in $PSPACE$ for a random oracle.


Is it also true that $PP^{PH}$ is properly contained in $PSPACE$ relative to a random oracle?


  1. From what I understand, this can be proved by showing that "small" $AC^{0}$ circuits with a MAJORITY gate at the root fail to compute the PARITY function even on a (1/2+small)-fraction of inputs. I found such claim in Theorem 6 of [3]. Does this reasoning make sense? Am I interpreting Klivans' theorem in the right way?

  2. I wrote "largest" class in the title, because I am also interested in classes that have this same property and that are uncomparable with $PP^{PH}$.


  1. Nostalgia for 90s research :)
  2. I am looking at similar questions in quantum complexity theory.


  1. Frederic Green, An oracle separating $\oplus P$ from $PP^{PH}$, Information Processing Letters, '91

  2. James Aspnes, Richard Beigel, Merrick Furst, and Steven Rudich, The expressive power of voting polynomials, STOC '91

  3. Adam Klivans, On the Derandomization of Constant Depth Circuits, RANDOM '01

  • 4
    $\begingroup$ +1 for nostalgia for 90s research (except it's really kind of 80s-style :)). I think I'll always have a place in my heart for that stuff - I'd always go to my advisor and ask some (80s-style, not that I realized it) question, and he'd always say it was too bad I wasn't a Ph.D. student in the 80s :). $\endgroup$ Oct 31 '14 at 20:27
  • $\begingroup$ @JoshuaGrochow I agree with you, oracle complexity is more 80s to be honest, '91 was just the tail of it. Should I create a tag [[80s]]? :P Happy Halloween! $\endgroup$ Oct 31 '14 at 20:53
  • 1
    $\begingroup$ @JoshuaGrochow Oh, and a trick: put a "Quantum" in front of your questions, people will think you're a modern kid :) $\endgroup$ Oct 31 '14 at 20:56
  • 1
    $\begingroup$ unjustified speculation regarding your title: I imagine that IP with a CH verifier is properly contained in PSPACE relative to a random oracle, although I have no idea how one might prove that. $\;$ $\endgroup$
    – user6973
    Nov 2 '14 at 0:16
  • $\begingroup$ @RickyDemer »IP with a CH verifier« Can you elaborate on what that means? $\endgroup$ Nov 2 '14 at 3:49

Yes, because $PP^{PH}=PP$ relative to a random oracle. Follows from Toda-Ogihara

  • $\begingroup$ Thank you! I wonder if that can be scaled down to some argument about $AC^{0} + MAJ$ circuits vs. voting polynomials. $\endgroup$ Nov 1 '14 at 20:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.