../
2026-11-16 TOC Scribe
Terse Notes
- $\mathbf{MIP} =\mathbf{NEXP}$. Having multiple provers is a superpower.
- We proved a weaker version of the PCP theorem $\mathbf{NP} \subset \mathbf{PCP}(\mathsf{poly}(n), 1)$
- The regular PCP theorem only uses $\log n$ random coins. So we’re using exponentially more than the original version but this is fine.
- We saw a concrete instantiation of this with Quadratic Equations
- In particular quadratic equations in $\text{GF}(2)$
- The general form is $A \in \text{GF}(2)^{m \times n^2}, b\in\text{GF}(2)^m$ and some $u\in\text{GF}(2)^n$ such that $A\odot(\vec{u}\otimes\vec{u})= \vec{b}$
PCP proof for QE
- The proof string $\pi = \text{WH}(u), \text{WH}(u\otimes u)$
- We call the first part $f = \text{WH}(u)$
- We call the second part $g = \text{WH}(u\otimes u)$
Phase 1: Linearity check
- $x_1, x_2 \gets \{0, 1\}^n$
- Check $f(x_1) + f(x_2) = f(x_1 + x_2)$
- Check $g(x_1) + g(x_2) = g(x_1 + x_2)$
- Repeat $O(1)$ times
Phase 2: Quadratic Check
- $x_1, x_2 \gets \{0, 1\}^n$
- Check $f(x_1)f(x_2) = g(x_1 \otimes x_2)$
- Repeat $O(1)$ times
Phase 3: Good Solution Test
- Sample $a', b'\in \text{RowSpan}(A, b)$
- Check if $g(a') = b'$
- Repeat $O(1)$ times