A Structural Theorem for Local Algorithms with Applications to Coding, Testing, and Privacy

by Marcel Dall'Agnol, Tom Gur, and Oded Lachish.

Oded's comments

I got confused by the first application; that is, the application to relaxed Locally Decodable Codes (RLDCs). The point is that the lower bound of Gur and Lachish applied to non-adaptive algorithms, whereas the straightforward transformation from adaptive to non-adaptive algorithms incures an exponential increase in the (Boolean) query complexity.

Related posts: lower bound for non-adaptive RLDC and best known RLDC.

The original abstract

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.

Our techniques strongly rely on relaxed sunflower lemmas and the Hajnal=E2=80=93Szemer=C3=A9di theorem.

Available from ECCC TR20-154.

Back to list of Oded's choices.