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 codewords, 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.