Can I read A Structural Theorem for Local Algorithms with Applications to Coding, Testing, and Privacy on EtoBox?

A Structural Theorem for Local Algorithms with Applications to Coding, Testing, and Privacy by Marcel Dall'Agnol; Tom Gur; Oded Lachish is a book available to read on EtoBox.

What is A Structural Theorem for Local Algorithms with Applications to Coding, Testing, and Privacy about?

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 samplebased algorithm with n 1-1/O(q 2 log 2 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 o

Author

Marcel Dall'Agnol; Tom Gur; Oded Lachish

Published

2021

Language

EN