Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA)
Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA)
复制标题
2021 年 ACM-SIAM 离散算法研讨会 (SODA) 论文集
DOI：
10.1137/1.9781611976465.100
复制
发表时间：
2021
期刊：
影响因子：
--
通讯作者：
Dall'Agnol M
中科院分区：
文献类型：
--
作者：
Dall'Agnol M
我们证明了一个一般的结构定理，广泛的家庭的本地算法，其中包括属性测试，本地解码器，概率可检查的证明接近。也就是说，我们证明了每个算法的结构，使自适应查询，并满足一个自然的鲁棒性条件承认一个基于样本的算法与样本复杂度，以下定义的Goldreich和罗恩[ACM Trans.计算。理论，8（2016），7]。我们证明了这种转换是接近最优的。我们的定理也承认一个计划，构建隐私保护的局部算法。使用统一的观点，我们的结构定理提供，我们得到的结果，各种类型的本地算法，包括以下。我们加强了放松的局部可解码代码的最新下界，在查询复杂度的依赖性上获得了指数级的改进;这解决了Gur和Lachish [SIAM J. Comput.，50（2021），pp. 788-813]。我们证明了任何（常量查询）可测试属性都允许具有次线性样本复杂度的基于样本的测试器;这解决了Fischer，Lachish和Vasudev的工作中遗留的问题[Proceedings of the 56 th Annual Symposium on Foundations of Computer Science，IEEE，2015，pp. 1163-1182]，绕过了在自适应测试器的情况下由先前技术引起的指数爆破。我们证明了邻近性证明和测试者之间的已知分离本质上是最大的;这解决了Gur和Rothblum [Proceedings of the 8 th Innovations in Theoretical Computer Science Conference，2017，pp. 39：1-39：43;计算。复杂性，27（2018），pp。99-207]关于计算的次线性时间委托。我们的技术强烈依赖于放松的向日葵引理和Hajnal-Szemerédi定理。
We prove a general structural theorem for a wide family of local algorithms, which includes property testers, local decoders, and probabilistically checkable proofs of proximity. Namely, we show that the structure of every algorithm that makesadaptive queries and satisfies a natural robustness condition admits a sample-based algorithm withsample complexity, following the definition of Goldreich and Ron [ACM Trans. Comput. Theory, 8 (2016), 7]. 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 anexponentialimprovement on the dependency in query complexity; this resolves an open problem raised by Gur and Lachish [SIAM J. Comput., 50 (2021), pp. 788–813]. 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 [Proceedings of the56th Annual Symposium on Foundations of Computer Science, IEEE, 2015, pp. 1163–1182], bypassing an exponential blowup caused by previous techniques in the case of 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 [Proceedings of the8th Innovations in Theoretical Computer Science Conference, 2017, pp. 39:1–39:43;Comput. Complexity, 27 (2018), pp. 99–207] regarding sublinear-time delegation of computation. Our techniques strongly rely on relaxed sunflower lemmas and the Hajnal–Szemerédi theorem.