Lower Bounds for Error-Correcting Codes with Local Recovery

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.