Query-efficient locally decodable codes of subexponential length

• Main Authors: Chee, Yeow Meng, Feng, Tao, Ling, San, Wang, Huaxiong, Zhang, Liang Feng
• 其他作者: School of Physical and Mathematical Sciences
• 格式: Article
• 語言: English
• 出版: 2012
• 主題: DRNTU::Science::Mathematics
• 在線閱讀: https://hdl.handle.net/10356/94604; http://hdl.handle.net/10220/7636
• 機構: Nanyang Technological University

A k-query locally decodable code (LDC) C : Σn → ΓN encodes each message x into a codeword C(x) such that each symbol of x can be probabilistically recovered by querying only k coordinates of C(x), even after a constant fraction of the coordinates has been corrupted. Yekhanin (2008) constructed a 3-q...