Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > AUTHORS > TAL YANKOVITZ:
All reports by Author Tal Yankovitz:

TR20-084 | 31st May 2020
Gil Cohen, Tal Yankovitz

Rate Amplification and Query-Efficient Distance Amplification for Locally Decodable Codes

In a seminal work, Kopparty et al. (J. ACM 2017) constructed asymptotically good $n$-bit locally decodable codes (LDC) with $2^{\widetilde{O}(\sqrt{\log{n}})}$ queries. A key ingredient in their construction is a distance amplification procedure by Alon et al. (FOCS 1995) which amplifies the distance $\delta$ of a code to a constant at ... more >>>




ISSN 1433-8092 | Imprint