论文标题
用于编码，测试和验证应用的本地算法的结构定理
A Structural Theorem for Local Algorithms with Applications to Coding, Testing, and Verification
论文作者
论文摘要
我们证明了广泛的本地算法家族的一般结构定理，其中包括属性测试人员，本地解码器和接近度PCP。也就是说，我们表明，在Goldreich和Ron（toct 2016）的定义之后，我们表明每种制作$ q $自适应查询算法的结构并满足具有$ n^{1- 1/o（q^2 \ log^2 q）$样品复杂性的基于样本的算法（q^2 \ log^2 q）} $（toct 2016）的基于样本的算法。我们证明这种转换几乎是最佳的。我们的定理还承认了一个构建隐私算法的计划。使用我们的结构定理提供的统一观点，我们获得有关各种局部算法的结果，包括以下内容。 - 我们为放松的本地可解码代码增强了最新的下限，从而获得了对查询复杂性的依赖性的指数改善；这解决了古尔（Gur）和拉奇什（Lachish）提出的一个空旷的问题（Sicomp 2021）。 - 我们表明，任何（恒定）可测试的属性都允许具有均方根样品复杂性的基于样本的测试仪；这解决了Fischer，Lachish和Vasudev（Focs 2015）的作品中的问题，将其主要结果扩展到适应性测试人员。 - 我们证明，邻近和测试仪证明之间的已知分离本质上是最大的。这解决了Gur and Rothblum（ECCC 2013，计算复杂性2018）剩下的问题，该问题涉及计算时间委托。 我们的技术强烈依赖于放松的向日葵引理和Hajnal-szemerédi定理。
We prove a general structural theorem for a wide family of local algorithms, which includes property testers, local decoders, and PCPs of proximity. Namely, we show that the structure of every algorithm that makes $q$ adaptive queries and satisfies a natural robustness condition admits a sample-based algorithm with $n^{1- 1/O(q^2 \log^2 q)}$ sample complexity, following the definition of Goldreich and Ron (TOCT 2016). We prove that this transformation is nearly optimal. Our theorem also admits a scheme for constructing privacy-preserving local algorithms. Using the unified view that our structural theorem provides, we obtain results regarding various types of local algorithms, including the following. - We strengthen the state-of-the-art lower bound for relaxed locally decodable codes, obtaining an exponential improvement on the dependency in query complexity; this resolves an open problem raised by Gur and Lachish (SICOMP 2021). - We show that any (constant-query) testable property admits a sample-based tester with sublinear sample complexity; this resolves a problem left open in a work of Fischer, Lachish, and Vasudev (FOCS 2015) by extending their main result to adaptive testers. - We prove that the known separation between proofs of proximity and testers is essentially maximal; this resolves a problem left open by Gur and Rothblum (ECCC 2013, Computational Complexity 2018) regarding sublinear-time delegation of computation. Our techniques strongly rely on relaxed sunflower lemmas and the Hajnal-Szemerédi theorem.
