A structural theorem for local algorithms with applications to coding, testing and delegation

Abstract

Motivated by the applicability of relaxed sunflower techniques to property testing and local decoding, we define a common framework that captures a wide family of local algorithms, encompassing those as well as proofs of proximity. This enables us to show that the structure of every algorithm that makes a constant number of adaptive queries and satisfies a natural robustness condition admits a sample-based algorithm with sublinear sample complexity; moreover, this transformation is nearly optimal.

The talk will give an overview of the general framework and the transformation from adaptive to sample-based algorithms, which relies heavily on relaxed sunflower lemmas and the Hajnal-Szemerédi theorem. Applying this transformation to particular cases, we obtain: (1) a strengthening of the state-of-the-art lower bound for relaxed locally decodable codes that improves the dependency in query complexity exponentially; (2) a transformation of any constant-query tester into a sample-based tester with sublinear sample complexity, that was previously known to hold only for non-adaptive testers; and (3) a limit on the power of sublinear-time delegation of computation, by showing almost tightness of the known separation between testers and proofs of proximity.

Joint work with Tom Gur and Oded Lachish.