Exponential sized graph 3-coloring is in MIP

Question

I was watching a talk by Anand Natarajan on $\text{NEEXP} \subseteq \text{MIP*}$, and he uses $\text{3-coloring}$ as an example problem for $\text{NEXP} = \text{MIP}$ (timestamp 3:50). He mentioned that a two-prover interactive system could solve an exponential-sized graph's $\text{3-coloring}$ problem. I have two questions regarding this:

1. If this proves $\text{NEXP} = \text{MIP}$, then is this problem $\text{NEXP-complete}$?
2. By inputting an exponential-sized graph, will it not make the input exponential-sized by default?

Answer 1

2. This is meant to use a succinct encoding of the graph. That is, a graph on $2^n$ vertices $V=\{0,1\}^n$ with an edge set $E\subseteq\{0,1\}^n\times\{0,1\}^n$ is represented by a Boolean circuit $C$ in $2n$ variables such that $$(\vec a,\vec b)\in E\iff C(\vec a,\vec b)=1$$ for all $\vec a,\vec b\in\{0,1\}^n$. Ideally, you should think of $C$ having size polynomial in $n$. (Only a few graphs have a representation with such a small $C$, but this will be enough for the argument.)

1. Yes, 3-colourability of succinctly encoded graphs is NEXP-complete. This requires some work, but it can be shown using similar ideas as the NP-completeness of usual 3-colourability. (In particular, one has to show that the graphs expressing exponentially long computations of a Turing machine are sufficiently uniform so that they can be encoded by polynomially small circuits.)