Skip navigation
Please use this identifier to cite or link to this item:
Title: Lower Bounds for Error-Correcting Codes with Local Recovery
Authors: Hu, Guangda
Advisors: Dvir, Zeev
Contributors: Computer Science Department
Keywords: Error-correcting codes
Locally decodable codes
Maximally recoverable codes
Subjects: Computer science
Issue Date: 2017
Publisher: Princeton, NJ : Princeton University
Abstract: Error-correcting codes (ECCs) are ubiquitous in computer science. A common property of ECCs is local recovery, which demands that given a corrupted codeword, a single lost code symbol can be recovered by reading only a small part of the codeword. An intriguing problem is to find the most "efficient" ECCs (e.g., codes with short length, codes over a small alphabet) with certain types of local recovery. Both constructions and lower bounds have been proven in the literature. However, the problem is still largely open. In this thesis, we prove three lower bound results on different types of ECCs with local recovery: Firstly, we propose an approximate version of locally decodable codes (LDCs) and prove lower bounds that are similar to the known ones for traditional LDCs. The concerned approximate LDCs are over real numbers and they support recoveries by querying constant number of codeword symbols. The 2-query case (the bulk of our work) is partially related to the lower bound of constant query LDCs, which is a major open problem. Secondly, we generalize the Sylvester-Gallai (SG) theorem to a subspace version. Generally speaking, the setting of the SG theorem is equivalent to 2-query locally correctable codes (LCCs), and our generalization corresponds to the block version of 2-query LCCs. Thirdly, we consider a realistic storage model that is a unification of several families of codes studied in the literature. We prove negative results for codes that attain the maximal recovering capability under this model. Our lower bound rules out the possibility of constructions of efficient codes for most parameter settings. We will also explore some results in the construction direction in the appendix.
Alternate format: The Mudd Manuscript Library retains one bound copy of each dissertation. Search for these copies in the library's main catalog:
Type of Material: Academic dissertations (Ph.D.)
Language: en
Appears in Collections:Computer Science

Files in This Item:
File Description SizeFormat 
Hu_princeton_0181D_12013.pdf656.5 kBAdobe PDFView/Download

Items in Dataspace are protected by copyright, with all rights reserved, unless otherwise indicated.