## Universal Locally Verifiable Codes and $3$-Round Interactive Proofs
of Proximity for CSP

#### Webpage for a paper by Oded Goldreich and Tom Gur

#### Abstract

Universal locally testable codes ULTCs,
recently introduced in our companion paper,
are codes that admit local tests for membership in numerous possible subcodes,
allowing for testing properties of the encoded message.
In this work, we initiate the study of the NP analogue of these codes,
wherein the testing procedures are also given free access to a short proof,
akin the MA proofs of proximity of Gur and Rothblum (ITCS 2015).
We call such codes ``universal locally *verifiable* codes" (ULVCs).
A ULVC $C:\bitset^k \to \bitset^n$ for a family of functions
$\mathcal{F} = \left\{ f_i : \bitset^k \to \bitset \right\}_{i \in [M]}$
is a code such that for every $i \in [M]$,
membership in the subcode $\{ C(x):f_i(x) = 1\}$ can be verified locally
given an explicit access to a short (sublinear length) proof.

We show ULVCs of block length $\tildeO(n^2)$ for the family of all functions
expressible by $t$-ary constraint satisfaction problems ($t$-CSP)
over $n$ constraints and $k$ variables, with proof length
and query complexity $\tildeO(n^{2/3})$, where $t=O(1)$ and $n\ge k$.
In addition, we prove a lower bound of $p \cdot q = \tilde\Omega(k)$
for every polynomial length ULVC, having proof complexity $p$
and query complexity $q$, for such CSP functions.

Lastly, we give an application for interactive proofs of proximity (IPP),
introduced by Rothblum, Vadhan, and Wigderson (STOC 2013),
which are interactive proof systems wherein the verifier queries
only a sublinear number of input bits to the end of asserting that,
with high probability, the input is close to an accepting input.
Specifically, we show a 3-round IPP for the set of assignments
that satisfy fixed CSP instances, with sublinear communication
and query complexity, which we derive from our ULVC for CSP functions.

**Note (Nov'16):**
This work previously appeared as a part of our technical report,
which contained the foregoing results regarding ULVCs and IPPs
as well as results regarding ``universal locally *testable* codes''.
Since this combination caused the former notion and results to be missed,
we chose to split the original version into two parts.
The current part contains the material regarding ULTCs.
The part regarding ULTCs appears in a companion paper.

Back to
either Oded Goldreich's homepage
or general list of papers.