Query-efficient locally decodable codes of subexponential length

• Main Authors: Chee, Yeow Meng, Feng, Tao, Ling, San, Wang, Huaxiong, Zhang, Liang Feng
• Other Authors: School of Physical and Mathematical Sciences
• Format: Article
• Language: English
• Published: 2012
• Subjects: DRNTU::Science::Mathematics
• Online Access: https://hdl.handle.net/10356/94604; http://hdl.handle.net/10220/7636
• Institution: 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...