View article

Universal locally testable codes (universal-LTC s), recently introduced in our companion paper (CJTCS, 2018), are codes that admit local tests for membership in numerous subcodes, allowing for testing properties of the encoded message. Unfortunately, universal-LTC s suffer strong limitations, which motivate us to initiate, in this work, 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 (Computational Complexity 2018). We call such codes “universal locally verifiable codes”(universal-LVC s). A universal-LVC C:{0, 1} k→{0, 1} η for a family of functions F={f i:{0, 1} k→{0, 1}} i∈[M] is a code such that, for every i∈[M], membership in the subcode {C (x): f i (x)= 1} can be verified locally using explicit access to a short (sublinear length) proof. A universal-LVC can be viewed as providing an encoding …