## 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.

- 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=E2=80=93Szemer=C3=A9di theorem.
Available from
ECCC TR20-154.

Back to
list of Oded's choices.