7
$\begingroup$

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.

Question

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

Observations

  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}$.

Motivations

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

References

  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

Improve this question
$\endgroup$
9
  • 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$
    – Joshua Grochow
    Oct 31, 2014 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$
    – Alessandro Cosentino
    Oct 31, 2014 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$
    – Alessandro Cosentino
    Oct 31, 2014 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, 2014 at 0:16
  • $\begingroup$ @RickyDemer »IP with a CH verifier« Can you elaborate on what that means? $\endgroup$
    – Alessandro Cosentino
    Nov 2, 2014 at 3:49

1 Answer 1

Reset to default
10
$\begingroup$

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

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thank you! I wonder if that can be scaled down to some argument about $AC^{0} + MAJ$ circuits vs. voting polynomials. $\endgroup$
    – Alessandro Cosentino
    Nov 1, 2014 at 20:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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