All reports by Author Oded Lachish:

__
TR20-154
| 10th October 2020
__

Marcel Dall'Agnol, Tom Gur, Oded Lachish#### A Structural Theorem for Local Algorithms with Applications to Coding, Testing, and Privacy

__
TR19-056
| 11th April 2019
__

Tom Gur, Oded Lachish#### A Lower Bound for Relaxed Locally Decodable Codes

Revisions: 1

Marcel Dall'Agnol, Tom Gur, Oded Lachish

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

Tom Gur, Oded Lachish

A locally decodable code (LDC) C:{0,1}^k -> {0,1}^n is an error correcting code wherein individual bits of the message can be recovered by only querying a few bits of a noisy codeword. LDCs found a myriad of applications both in theory and in practice, ranging from probabilistically checkable proofs to ... more >>>