On the Power of Relaxed Local Decoding Algorithms
- Submitting institution
-
Birkbeck College
- Unit of assessment
- 11 - Computer Science and Informatics
- Output identifier
- 9999
- Type
- E - Conference contribution
- DOI
-
10.1137/1.9781611975994.83
- Title of conference / published proceedings
- Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms
- First page
- 1377
- Volume
- -
- Issue
- -
- ISSN
- -
- Open access status
- -
- Month of publication
- January
- Year of publication
- 2020
- URL
-
https://epubs.siam.org/doi/10.1137/1.9781611975994.83
- Supplementary information
-
-
- Request cross-referral to
- -
- Output has been delayed by COVID-19
- No
- COVID-19 affected output statement
- -
- Forensic science
- No
- Criminology
- No
- Interdisciplinary
- No
- Number of additional authors
-
1
- Research group(s)
-
1 - Algorithms, Verification and Software
- Citation count
- 2
- Proposed double-weighted
- No
- Reserve for an output with double weighting
- No
- Additional information
- This paper resolves an open problem raised by Goldreich in 2004. It studies a Relaxation of Locally Decodable Codes (LDC). This relaxation (RLDC) is currently essential since celebrated results for LDCs do not provide LDCs with sufficient parameters. However, RLDCs with very useful parameters had been demonstrated. Yet, until this paper there was no indication on how good these parameters can get. This paper provided the only known lower bound for the parameters of RLDCs. Bounds that are almost as strong as those for LDCs.
An archival version https://arxiv.org/pdf/1904.08112.pdf has been accepted for publication in SIAM J. on Computing.
- Author contribution statement
- -
- Non-English
- No
- English abstract
- -