Collapses under the assumption that $NEXP\subseteq P/Poly$

Question

It is known that if $NP\subseteq P/Poly$ then the polynomial hierarchy collapses to $\Sigma_2^{P}$ and $MA = AM$.

What are the strongest collapses known to happen if $NEXP\subseteq P/Poly$?

Answer 1

I believe the strongest is that $NEXP = MA$. This was proved by Impagliazzo Kabanets and Wigderson.

See https://scholar.google.com/scholar?cluster=17275091615053693892&hl=en&as_sdt=0,5&sciodt=0,5

I'd be also interested to know of any stronger collapses than this.

Edit (8/24): OK, I thought of some potentially stronger collapse, which essentially follows from the proofs of the above linked paper. Because $NEXP \subset P/poly$ implies $NEXP = EXP$ (see the above link), and $EXP$ is closed under complement, we also have $NEXP$ closed under complement and therefore $NEXP = MA \cap coMA$, which is a little stronger. Indeed, the hypothesis implies that for any $NEXP$ language, a single witness string $w_n$ can be used in the corresponding MA protocol for all YES-instances of any given length $n$, so also $NEXP = OMA \cap coOMA$ (where $OMA$ = "Oblivious MA", see Fortnow-Santhanam-me http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.156.3018&rep=rep1&type=pdf). These extra properties, while technical, could prove to be useful in some circuit lower bound argument.

Edit 2: Looks like Andrew Morgan highlighted this already. Whoops :)

Answer 2

A whole lot of fun things happen. Most of the ones I know of start with the IKW paper. There, the collapse $\textrm{NEXP} = \textrm{MA}$ is shown, and (I think) is the strongest literal collapse of complexity classes that we know of. There are other sorts of "collapses" though that I think should be pointed out.

Most importantly, I think, is the "universal succinct witness" property (also from the IKW paper). For one, it gives you a tool from which many of the other collapses are straightforward consequences; for another, the recent circuit lower bounds (eg here and here) for $\textsf{NEXP}$ exploit this connection. Briefly, the property says that, for every $\textsf{NEXP}$ language $L$, and any $\textsf{NEXP}$-machine $M$ deciding $L$, every $x \in L$ has a succinctly describable witness according to $M$. Formally, there is a polynomial $p$ depending on $M$ so that for every $x \in L$, there is a circuit $C_x$ of size $p(|x|)$ so that the truth table of $C_x$ is a sequence of nondeterministic choices for $M$ that lead to acceptance on input $x$.

The succinctness of the witnesses comes in handy, because you can straightforwardly rederive a lot of the other collapses from it. For instance, it follows trivially that $\textsf{NEXP} = \textsf{coNEXP} = \textsf{EXP}$. For example, suppose $L$ is in $\textsf{NEXP}$ via a $\textsf{NEXP}$-machine $M$. The succinct-witness property says there's a polynomial $p$ so that $M$ has succinct witnesses of size $p$. We can then decide $L$ in $\textsf{EXP}$ by, on input $x$, brute-forcing all the circuits of size at most $p(|x|)$, and checking whether they encode a sequence of choices that lead to $M$ accepting on input $x$. You can combine this with the (previously known via interactive proofs) result that $\textsf{EXP} \subseteq \textsf{P}/\textrm{poly} \implies \textsf{EXP} = \textsf{MA}$ to conclude $\textsf{NEXP} \subseteq \textsf{P}/\textrm{poly} \implies \textsf{NEXP} = \textsf{MA}$.

It's worth emphasizing that we get to pick $M$ and hence the form of the witnesses. For example, you can actually conclude from "$\textsf{NEXP}$ has universal succinct witnesses" that $\textsf{NEXP} = \textsf{OMA} = \textsf{co-OMA}$. Here $\textsf{OMA}$ is "oblivious-MA", meaning that there is an honest Merlin which depends only on the input length. It's easy to see that $\textsf{OMA} \subseteq \textsf{P}/\textrm{poly}$, so basically this is just giving a normal form for how $\textsf{NEXP}$ languages are computed in $\textsf{P}/\textrm{poly}$ under the assumption that $\textsf{NEXP} \subseteq \textsf{P}/\textrm{poly}$ in the first place. Here's one way to see the collapse to $\textsf{OMA}$:

For a language $L \in \mathsf{NEXP}$ decided by a machine $M$, construct a $\mathsf{NEXP}$ machine $M'$ as follows. View the $n$-bit input as a number $N$ between $1$ and $2^n$. For every $x$ of length $n$, guess a witness $w_x$ and run $M(x,w_x)$ to verify it. $M'(N)$ accepts if and only if $M$ accepts for at least $N$ values of $x$. The guesses are arranged such that a succinct description of a witness for $M'$ is a circuit $C$ which computes the map $(x,i) \mapsto$ the $i$-th bit of $w_x$. Now suppose that $N$ is precisely the number of strings in $L$ at length $n$. Then succinct witnesses for $M'$ on input $N$ are circuits that simultaneously encode all of $M$'s witnesses for length-$n$ inputs. In particular, if $M'$ has succinct witnesses, then all of $M$'s witnesses can be simultaneously described by the same circuit.

To complete the claim, we'll recall that $\textsf{NEXP} = \textsf{PCP}[\textrm{poly}, \textrm{poly}]$. Letting $M$ be the machine which guesses the PCP and then deterministically simulates the verifier, the above paragraph tells us the existence of simultaneously succinctly describable PCPs for every language in $\textsf{NEXP}$. So now to get $\textsf{NEXP} = \textsf{OMA}$, we have Merlin send the succinct description of the PCPs for all inputs of the current input length, which Arthur can check by just plugging in his input and then running the PCP verifier.

[Thanks to Cody Murray for pointing out the trick of using the input to count the number of strings in $L$. Previously I had $M'$ use that if $\mathsf{NEXP}\subseteq\mathsf{P/poly}$ then $\mathsf{NEXP}=\mathsf{EXP}$ to write down the truth table of $L$, but Cody's strategy is more elegant.]

As a final note, while technically implied by $\textsf{NEXP}=\textsf{MA}$, the collapse $\textsf{NEXP}=\textsf{PSPACE}$ has another interesting implication. It's known that $\textsf{PSPACE}$ has a complete language which is both downward self-reducible as well as random self-reducible. Ordinarily, all such languages sit inside $\textsf{PSPACE}$ and so we shouldn't hope to say (unconditionally) that $\textsf{NEXP}$ has such a complete language as long as we hope that $\textsf{NEXP} \ne \textsf{PSPACE}$. However, if $\textsf{NEXP} = \textsf{PSPACE}$, then $\textsf{NEXP}$ does have such complete languages. A similar statement (replacing $\textsf{NEXP}$ by $\textsf{EXP}$) was used by Impagliazzo and Wigderson to conclude a sort of "derandomization dichotomy" for $\textsf{BPP}$ in relation to $\textsf{EXP}$, so it may be useful in discovering other consequences of $\textsf{NEXP} \subseteq \textsf{P}/\textrm{poly}$.