Details for the IKW Theorem

The proof of the IKW Theorem I gave in class was a bit sketchy; let me discuss two points about it, raised by Or and Pranjal.

1. The first point, raised by Or, was about appealing to the Impagliazzo-Wigderson Theorem (or implicitly, the Nisan-Wigderson Theorem). Normally when one thinks about that theorem one thinks of the statement, "If there is a language $L \in E$ such that $L \not \in \bigcup_c \SIZE(n^c)$, then $BPP \subseteq \bigcap_{\epsilon} DTIME(2^{n^\epsilon})$.

However, this is not what the IKW Theorem appeals to; you should think of that as a corollary of the IW/NW Theorems. The Theorems themselves are input-length-specific; e.g., for Nisan-Wigderson, the statement we're using is of the form "Let $C$ be a circuit on $n$ bits of size $n^c$, and let $f : \{0,1\}^{n^{1/10c}} \to \{0,1\}$ be a function such that every size-$n^{2c}$ circuit has correlation at most $1/n^{2c}$. Then [some explicit PRG outputting $n$ bits based on $f$'s truth table and designs] $1/10$-fools $C$."

2. The second point, raised by Pranjal, was about the uncareful (indeed, possibly incorrect) way I explained the derandomization of $MA$ that comes out of assuming $NEXP \neq EXP$. The wrong way to say it is to start with a fixed language in $MA$ and then deduce that Arthur's $n^c$-time randomized part can be replaced by some other $NTIME(2^{n^a})$-time algorithm (with advice). That is, of course, pointless, if $a \geq c$, since Arthur could just enumerate all possible random strings. Rather, the key is to show that all of $MA$ can be done by a nondeterministic (advice-taking) Arthur who uses fixed-exponential nondeterministic time.

In other words, the correct key lemma is:

$NEXP \neq \EXP \Rightarrow \exists c, MA \subseteq io-[NTIME(2^{n^c})/n]$.

This is nontrivial because the same $c$ works for all languages in $MA$, regardless of their polytime complexity. And the proof of this uses the appeal to the length-specific IW Theorem described in Point 1 above.