../

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