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

Question

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)

Answer 1

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)} > 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?).