Relaxed Locally Correctable Codes in Computationally Bounded Channels
- 28 April 2021
- journal article
- research article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Information Theory
- Vol. 67 (7) , 4338-4360
Abstract
Error-correcting codes that admit local decoding and correcting algorithms have been the focus of much recent research due to their numerous applications. An important goal is to obtain the best possible tradeoffs between the number of symbols of the codeword that the local decoding algorithm must examine (the locality), and the amount of redundancy in the encoding (the information rate). In Hamming's classical adversarial channel model, the current tradeoffs are dramatic, allowing either small locality but superpolynomial blocklength, or small blocklength but high locality. However, in the computationally bounded adversarial channel model, proposed by Lipton (STACS 1994), constructions of locally decodable codes suddenly exhibit small locality and small blocklength, but these constructions require strong trusted setup assumptions. We study variants of locally decodable and locally correctable codes in computationally bounded, adversarial channels, in a setting with no trusted setup. The only assumption we require is the selection of the public parameters (seed) for a collision-resistant hash function. Specifically, we provide constructions of relaxed locally correctable and relaxed locally decodable codes over the binary alphabet, with constant information rate, and poly-logarithmic locality. Our constructions, which compare favorably with their classical analogs, crucially employ collision-resistant hash functions and local expander graphs, extending ideas from recent cryptographic constructions of memory-hard functions.Keywords
Funding Information
- National Science Foundation (CNS-1755708, CCF-1910659)
- National Science Foundation (CCF-1649515, CCF-1910659, CCF-1910411)
- Purdue Research Foundation
- National Science Foundation (CCF-1649515)
- Simons Investigator Award of David P. Woodruff
This publication has 47 references indexed in Scilit:
- Two-query PCP with subconstant errorJournal of the ACM, 2008
- Towards 3-query locally decodable codes of subexponential lengthJournal of the ACM, 2008
- Exponential lower bound for 2-query locally decodable codes via a quantum argumentJournal of Computer and System Sciences, 2004
- Private information retrievalJournal of the ACM, 1998
- Expander codesIEEE Transactions on Information Theory, 1996
- Designing programs that check their workJournal of the ACM, 1995
- Self-testing/correcting with applications to numerical problemsJournal of Computer and System Sciences, 1993
- Algebraic methods for interactive proof systemsJournal of the ACM, 1992
- On sparse graphs with dense long pathsComputers & Mathematics with Applications, 1975
- Class of constructive asymptotically good algebraic codesIEEE Transactions on Information Theory, 1972