  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
(SICOMP 2021).
  - 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\'edi theorem.
