TY - GEN

T1 - A structural theorem for local algorithms with applications to coding, testing, and privacy

AU - Dall'Agnol, Marcel

AU - Gur, Tom

AU - Lachish, Oded

N1 - Funding Information:
Tom Gur is supported by the UKRI Future Leaders Fellowship MR/S031545/1.
Publisher Copyright:
Copyright © 2021 by SIAM

PY - 2021

Y1 - 2021

N2 - 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 n1−1/O(q2 log2 q) sample complexity. We also prove that this transformation is nearly optimal, and admits a scheme for constructing privacy-preserving local algorithms. Using the unified view that our structural theorem provides, we obtain the following results. • 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 (SODA 2020). • 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.

AB - 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 n1−1/O(q2 log2 q) sample complexity. We also prove that this transformation is nearly optimal, and admits a scheme for constructing privacy-preserving local algorithms. Using the unified view that our structural theorem provides, we obtain the following results. • 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 (SODA 2020). • 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.

UR - http://www.scopus.com/inward/record.url?scp=85105342743&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85105342743&partnerID=8YFLogxK

M3 - Conference contribution

AN - SCOPUS:85105342743

T3 - Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

SP - 1651

EP - 1665

BT - ACM-SIAM Symposium on Discrete Algorithms, SODA 2021

A2 - Marx, Daniel

PB - Association for Computing Machinery

T2 - 32nd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2021

Y2 - 10 January 2021 through 13 January 2021

ER -