<p>Yes, because $PP^{PH}=PP$ relative to a random oracle. Follows from <a href="http://dx.doi.org/10.1137/0221023">Toda-Ogihara</a></p>

CC BY-SA 3.0
2014-11-01T20:59:53.133Z
Thank you! I wonder if that can be scaled down to some argument about $AC^{0} + MAJ$ circuits vs. voting polynomials.
Alessandro Cosentino
CC BY-SA 3.0
2014-10-31T23:56:11.807Z
2014-10-31T23:56:11.807Z
Lance Fortnow
<p>Green [1] showed that $PP^{PH}$ is properly contained in $PSPACE$ relative to <em>some</em> oracle. Around the same time, in the famous "voting polynomials" paper [2], it was shown that $PP$ is properly contained in $PSPACE$ for a <em>random</em> oracle.</p>

<h2>Question</h2>

<blockquote>
  <p>Is it also true that $PP^{PH}$ is properly contained in $PSPACE$ relative to a <em>random</em> oracle?</p>
</blockquote>

<h2>Observations</h2>

<ol>
<li><p>From what I understand, this can be proved by showing that "small" $AC^{0}$ circuits with a <strong>MAJORITY</strong> gate at the root fail to compute the <strong>PARITY</strong> 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?</p></li>
<li><p>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}$.</p></li>
</ol>

<h2>Motivations</h2>

<ol>
<li>Nostalgia for 90s research :)</li>
<li>I am looking at similar questions in quantum complexity theory.</li>
</ol>

<h2>References</h2>

<ol>
<li><p>Frederic Green, <a href="http://www.clarku.edu/~fgreen/papers/tac.ps">An oracle separating $\oplus P$ from $PP^{PH}$</a>, Information Processing Letters, '91</p></li>
<li><p>James Aspnes, Richard Beigel, Merrick Furst, and Steven Rudich, <a href="http://www.cs.yale.edu/homes/aspnes/papers/stoc91voting-abstract.html">The expressive power of voting polynomials</a>, STOC '91</p></li>
<li><p>Adam Klivans, <a href="https://www.cs.utexas.edu/~klivans/ac3.ps">On the Derandomization of Constant Depth Circuits</a>, RANDOM '01</p></li>
</ol>

CC BY-SA 3.0
2014-10-31T20:27:31.523Z
+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 :).
Joshua Grochow
CC BY-SA 3.0
2014-10-31T20:53:57.990Z
@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!
Alessandro Cosentino
CC BY-SA 3.0
2014-10-31T20:56:46.707Z
@JoshuaGrochow Oh, and a trick: put a "Quantum" in front of your questions, people will think you're a modern kid :)
Alessandro Cosentino
CC BY-SA 3.0
2014-11-02T03:49:55.257Z
@RickyDemer »IP with a CH verifier« Can you elaborate on what that means?
Alessandro Cosentino
CC BY-SA 3.0
2014-11-02T04:03:29.203Z
@RickyDemer That's what I had understood. Isn't that a much bigger class than IP?
Alessandro Cosentino
CC BY-SA 3.0
2014-11-02T04:43:35.147Z
@RickyDemer I see, thanks for the explanation. Come to think of it, the title doesn't make much sense if I think about IP. I will have to edit it.
Alessandro Cosentino
<cc.complexity-theory><circuit-complexity><random-oracles>
"Largest" class properly contained in PSPACE for a random oracle
Alessandro Cosentino
# "Largest" class properly contained in PSPACE for a random oracle

(Asked by: username_0 on 2014-10-31)

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}$](http://www.clarku.edu/~fgreen/papers/tac.ps), Information Processing Letters, '91
2. James Aspnes, Richard Beigel, Merrick Furst, and Steven Rudich, [The expressive power of voting polynomials](http://www.cs.yale.edu/homes/aspnes/papers/stoc91voting-abstract.html), STOC '91
3. Adam Klivans, [On the Derandomization of Constant Depth Circuits](https://www.cs.utexas.edu/~klivans/ac3.ps), RANDOM '01

**Tags:** cc.complexity-theory, circuit-complexity, random-oracles
> **Comments:**
> **username_1**: +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 :).  
> **username_0**: @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!  
> **username_0**: @JoshuaGrochow Oh, and a trick: put a "Quantum" in front of your questions, people will think you're a modern kid :)  
> **username_0**: @RickyDemer »IP with a CH verifier« Can you elaborate on what that means?  
> **username_0**: @RickyDemer That's what I had understood. Isn't that a much bigger class than IP?  
> **username_0**: @RickyDemer I see, thanks for the explanation. Come to think of it, the title doesn't make much sense if I think about IP. I will have to edit it.  

---

## 1 answers

### Answer by username_2 on 2014-10-31. Score: 10 | Accepted answer

Yes, because $PP^{PH}=PP$ relative to a random oracle. Follows from [Toda-Ogihara](http://dx.doi.org/10.1137/0221023)

> **Comments:**
> **username_0**: Thank you! I wonder if that can be scaled down to some argument about $AC^{0} + MAJ$ circuits vs. voting polynomials.  

---

