Target-Dependent Local Verification: Information--Proof-Length Tradeoffs

Abstract

We study fixed-layout local verification with target-dependent local tests. Let $M$ be a random variable on $\{0,1{\}}^K$, and let $S$ record the test selected at each coordinate. For each $s\in \mathrm{supp}(S)$, let $F_s$ be the corresponding target fiber and set $D_{\mathrm{fib}}={\max }_s\mathrm{VCdim}(F_s)$. We prove $H(M\mid S)\le {\log }_2\left({\sum }_{j=0}^{D_{\mathrm{fib}}}\left(\genfrac{}{}{0ex}{}{K}{j}\right)\right)$. A fiber that shatters $d$ coordinates yields a weak relaxed locally decodable code with message length $d$ and block length $d+P$ over the original proof alphabet. For a uniform $K$-bit target and fixed proof alphabet, $Q$, and $\sigma$, the Goldberg--Gur--Saraogi lower bound implies that $I(M;S)\le \gamma K$, for fixed $\gamma <1$, forces $P=\Omega \left(K^{1+1/a}/(\log K{)}^{2+2/a}\right)$, where $a=\lceil Q/\sigma \rceil$. If $P\le K(\log K{)}^c$, then $I(M;S)\ge K-O\left(K^{a/(a+1)}(\log K{)}^{3+ac/(a+1)}\right)=K-o(K)$. Any discrete verifier state $T$ determining $S$ satisfies the same information lower bound. Bounded-randomness adaptive branches can be simulated nonadaptively by exposing their decision trees. A branch using at most $r$ random bits and $q$ adaptive proof queries yields a decoder with perfect completeness and at most $1+2^{r+1}{\sum }_{j<q}{A}^j$ queries. Under $I(M;S)\le \gamma K$, near-linear proof length requires this quantity to be $\Omega (\log K/\log \log K)$; the binary one-query case gives $P=2^{\Omega (K)}$. Applied to a global list-sound dPCP interface of Gur--Minzer--Weissenberg--Zheng, our bound shows that a fixed target-independent menu of $L$ test profiles must satisfy ${\log }_{2}L\ge K-o(K)$. Proof-dependent lists and additional target-dependent selection data must be included in the measured state.

15 pages. Submitted to computational complexity