On Locally Decodable Codes, Self-Correctable Codes, and t-Private PIR |
| |
Authors: | Omer Barkol Yuval Ishai Enav Weinreb |
| |
Affiliation: | 1. Dept. of Computer Science, Technion, Haifa, Israel 2. HP Labs, Haifa, Israel 3. Dept. of Computer Science, University of California, Los Angeles, USA
|
| |
Abstract: | A k-query locally decodable code (LDC) allows to probabilistically decode any bit of an encoded message by probing only k bits of its corrupted encoding. A stronger and desirable property is that of self-correction, allowing to efficiently recover not only bits of the message but also arbitrary bits of its encoding. In contrast to the initial constructions of LDCs, the recent and most efficient constructions are not known to be self-correctable. The existence of self-correctable codes of comparable efficiency remains open. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|