What is the minimum complexity oracle that separates PSPACE from the polynomial hierarchy? Background


  It is known that there exists an oracle $A$ such that, $PSPACE^A \neq PH^A$.
  
  It is even known that the separation holds relative to a random
  oracle.  Informally, one may interpret this to mean that there are
  many oracles for which $PSPACE$ and $PH$ are separate.


Question


  How complicated are these oracles that separate $PSPACE$ from $PH$. 
  In particular, is there an oracle $A \in DTIME(2^{2^{n}})$ such that
  $PSPACE^A \neq PH^A$?
  
  Do we have any oracle $A$ such that $PSPACE^A \neq PH^A$ and $A$ has a known complexity upper bound?


Note: the existence of such an oracle may have ramifications in structural complexity theory.  See the following update below for further details.

Update with details on a lower bound technique

Claim: If $PSPACE = PH$, then for all oracles $A \in P/poly$, $PSPACE^A = PH^A$.


  Proof Sketch: Suppose that $PSPACE = PH$.
  
  Let an oracle $A \in P/poly$ be given.  We can build a polynomial time
  $\Sigma_2$ oracle Turing machine $M$ that for a given length $n$,
  guesses a circuit of size $p(n)$ using an existential quantification
  and verifies that the circuit decides $A$ by comparing the evaluation of the circuit and the query result for every length $n$ string
  using a universal quantification.
  
  Further, consider a decision problem that I'm referring to as
  quantified Boolean circuit (QBC) where you are given a quantified
  boolean circuit and want to know if it valid (similar to QBF).  This
  problem is PSPACE-complete because QBF is PSPACE-complete.
  
  By assumption, it follows that QBC $\in PH$.  Let's say $QBC \in
\Sigma_k$ for some $k$ sufficiently large.  Let $N$ denote a
  polynomial time $\Sigma_k$ Turing machine that solves QBC.
  
  We can intermingle the computation of $M$ and $N$ (similar to what is
  done in the proof of the Karp-Lipton theorem) to get a polynomial time
  $\Sigma_k$ oracle Turing machine that solves $QBC^A$.
  
  Informally, this new machine takes as input an oracle QBC (that is a
  QBC with oracle gates).  Then, it computes a circuit that computes
  $A$ on inputs of length $n$ (simultaneously pealing off the first two
  quantifiers).  Next, it replaces the oracle gates in the oracle QBC
  with the circuit for $A$.  Finally, it proceeds to apply the remainder
  of the polynomial time $\Sigma_k$ algorithm for solving $QBC$ on this
  modified instance.


Now, we can show the conditional lower bound.

Corollary: If there exists an oracle $A \in NEXP$ such that $PSPACE^A \neq PH^A$, then $NEXP \nsubseteq P/poly$.


  Proof Sketch: Suppose that there exists $A \in NEXP$ such that $PSPACE^A \neq PH^A$. If $NEXP \subseteq P/poly$, then we would get a contradiction. 
  
  In particular, if $NEXP \subseteq P/poly$, then by the claim above we
  have $PSPACE \neq PH$.  However, it is known that $NEXP \subseteq P/poly$ implies that $PSPACE = PH$.
  
  (see here for some details on known results for P/poly)
I believe if you trace through the argument given, e.g., in Section 4.1 of Ker-I Ko's survey, you get an upper bound of $\mathsf{DTIME}(2^{2^{O(n^2)}})$. In fact, we can replace $n^2$ here with any function $nf(n)$ where $f(n) \to \infty$ as $n \to \infty$. This isn't quite what was asked for, but it's close.

In particular, using the translation between oracle separations and circuit lower bounds, and following Ko's notation, we have the following:


We will diagonalize over strings of length $t(n) = p_n(m(n))$ where $p_n(x) = x^n + n$ is "the" $n$-th polynomial (in some enumeration of poly-time algorithms) and $m(n)$ will be specified below.
Translating into circuit lower bounds, this means we're considering bounded-depth circuits on $2^{t(n)}$ inputs.
The requirement (see p. 15 of Ko) we need $m(n)$ to satisfy $\frac{1}{10} 2^{m/(d-1)} &gt; d p_n(m(n))$ for all $n$. Here $d$ is the depth of the circuits we want to diagonalize against, or equivalently the level $\mathsf{\Sigma_d^p}$ of $\mathsf{PH}$ we want to diagonalize against. To diagonalize against all of $\mathsf{PH}$, simply choose $d$ to be a function of $n$ that is $\omega(1)$; we may choose such a $d$ that grows arbitrarily slowly, though (perhaps subject to some computability assumption on $d(n)$, but that should be no obstacle). If we make the guess that $d(n)$ is constant (even though it's not, but it will grow arbitrarily slowly), then we see that $m(n)$ around $2^n$ should work.
This means that $t(n) \sim 2^{n^2}$, so we are looking for a lower bound against circuits with $\sim 2^{2^{n^2}}$ inputs.
Trevisan and Xue (CCC '13) showed that one can find an assignment on which a given bounded-depth circuit on $N$ inputs doesn't compute PARITY with a seed of $polylog(N)$ length.
For us $N=2^{2^{n^2}}$, so $polylog(N) = 2^{O(n^2)}$. We can brute force over such seeds in $2^{2^{O(n^2)}}$ time and use the first one that works.


To replace the $n^2$ with $nf(n)$, just let $p_n(x) = x^{f(n)} + f(n)$ instead.

Interestingly, if I'm understanding correctly, I believe this implies that if one could improve the Trevisan-Xue...


...to a pseudodeterministic/Bellagio algorithm (see Andrew Morgan's comment below), one would get that $\mathsf{BPEXP} \not\subseteq \mathsf{P/poly}$; or
...to a nondeterministic algorithm that guessed $polylog(N)$ bits but then ran in $poly(N)$ time, and such that on any accepting path it makes the same output (cf. $\mathsf{NPSV}$), it would imply $\mathsf{NEXP} \not\subseteq \mathsf{P/poly}$; or
... to a deterministic algorithm, one would get $\mathsf{EXP} \not\subseteq \mathsf{P/poly}$.


On the one hand, this suggests why derandomizing the switching lemma further should be hard - an argument which I'm not sure was known before! On the other hand, this strikes me as a kind of interesting take on hardness versus randomness (or is this actually a new thing, oracles versus randomness?).