$\mathrm{strict}$-$\mathrm{SUBEXP} \subset \mathrm{P}/\mathrm{poly} \implies \mathrm{strict}$-$\mathrm{SUBEXP} \subset \mathrm{MA}$

Question

Is anyone able to give a concise proof for the implication stated in the title? This is gonna be in stark contrast to this question.

---

For definition of $\mathrm{strict}$-$\mathrm{SUBEXP}$, see here.

Answer 1

Yes, I can.

First of all, $\mathrm{poly}(\mathrm{subexp}) = \mathrm{subexp}$. So, we can simulate a subexp TM in subexp time. (This is in stark contrast to standard $\mathrm{SUBEXP}$ where we do not have any particular subexp machine)

Using this, we are able to put $\mathrm{strict}$-$\mathrm{SUBEXP}$ inside $\mathrm{PSPACE}$. The poly space TM would try every possible poly-size circuit and for each circuit make $2^n \times 2^n$ local checking of the tableaux using the current circuit. Note that the subexp TM never touches the $2^n$th cell and would cease to run long before $2^n$ time but that does not affect the poly space bound.

After putting $\mathrm{strict}$-$\mathrm{SUBEXP}$ inside $\mathrm{PSPACE}$, we use the result of interactive proving protocol with the power of the prover at most $\mathrm{P}^\mathrm{L}$ (where $\mathrm{L}$ is the language at hand) to push it down to $\mathrm{MA}$.