A STRUCTURAL THEOREM FOR LOCAL ALGORITHMS WITH APPLICATIONS TO CODING, TESTING, AND VERIFICATION


Type
Article
Change log
Authors
Dall'Agnol, M 
Lachish, O 
Abstract

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 makes q adaptive queries and satisfies a natural robustness condition admits a sample-based algorithm with n1-1/O(q2 log2 q) sample 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 an exponential improvement 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 the 56th 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 the 8th 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.

Description
Keywords
4613 Theory Of Computation, 4901 Applied Mathematics, 46 Information and Computing Sciences, 4903 Numerical and Computational Mathematics, 49 Mathematical Sciences
Journal Title
SIAM Journal on Computing
Conference Name
Journal ISSN
0097-5397
1095-7111
Volume Title
52
Publisher
Society for Industrial & Applied Mathematics (SIAM)
Sponsorship
UK Research and Innovation (MR/S031545/1)