Universal locally verifiable codes and 3-round interactive proofs of proximity for CSP
Universal locally verifiable codes and 3-round interactive proofs of proximity for CSP
复制标题
CSP 的通用本地可验证代码和 3 轮交互式邻近证明
DOI：
10.1016/j.tcs.2021.05.030
复制
发表时间：
2021
影响因子：
1.1
通讯作者：
Goldreich O
中科院分区：
文献类型：
--
作者：
Goldreich O
最近在我们的同伴论文（CJTCS，2018）中介绍的通用局部可测试代码（universal-LTC）是允许对众多子码中的成员进行局部测试的代码，允许测试编码消息的属性。不幸的是，通用LTC受到很大的限制，这促使我们在这项工作中开始研究这些代码的“NP模拟”，其中测试程序也可以免费获得简短的证明，类似于Gur和Rothblum的近似MA证明（计算复杂性2018）。我们称这种代码为“通用本地可验证代码”（通用LVC）。函数族F={fi：{0，1} k→{0，1}} i∈[M]的泛LVC C：{0，1} k→{0，1} η是一个码，使得对于每个i∈[M]，子码{C（x）：fi（x）= 1}中的成员可以使用显式访问短（次线性长度）证明来局部验证。通用LVC可以被视为提供输入的编码，在该编码下，编码输入的一大类属性可以使用简短证明来局部测试。证明了在n个约束和k个变量上，所有可由t元约束满足问题（t-CSP）表示的函数族的块长为O <$（n2）的泛LVC，证明长度和查询复杂度为O <$（n2/3），其中t= O（1），n≥ k.此外，对于证明复杂度为p，查询复杂度为q的多项式长度泛LVC，证明了p <$q= Ω <$（k）的下界.我们给出了Rothblum，Vadhan和Wigderson（STOC 2013）引入的交互式邻近证明（IPP）的通用LVC的应用，这是一种交互式证明系统，其中验证者仅查询输入位的次线性数量，以高概率断言输入接近接受输入。具体来说，我们展示了一个3轮IPP的一组任务，满足固定的CSP实例，次线性通信和查询的复杂性，我们从我们的通用LVC CSP功能。
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 of inputs under which a large family of properties of the encoded inputs can be locally testable using a short proof. We show universal-LVC s of block length O˜(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 O˜(n 2/3), where t= O (1) and n≥ k. In addition, we prove a lower bound of p⋅ q= Ω˜(k) for every polynomial length universal-LVC, having proof complexity p and query complexity q, for such CSP functions. We give an application of universal-LVC s 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 universal-LVC for CSP functions.