Please use this identifier to cite or link to this item: https://hdl.handle.net/10356/69693
Title: Local correction of codes of high rate
Authors: Wu, Liyasi
Keywords: DRNTU::Science::Mathematics
Issue Date: 2017
Source: Wu, L. (2017). Local correction of codes of high rate. Doctoral thesis, Nanyang Technological University, Singapore.
Abstract: Locally correctable codes (LCC) are error-correcting codes with efficient decoding schemes, which can recover any bit of a codeword by visiting a small number of locations of the codeword. LCCs have found numerous applications in complexity theory, cryptography and the theory of fault tolerant computation. In this work, we investigate the locally correctable codes of high rate. We are mainly interested in new constructions of high-rate locally correctable codes, local correction of multiple bits, and the inner connection between the lifted Reed-Solomon codes and the multiplicity codes. Firstly, we extend the techniques of lifted Reed-Solomon codes by lifting multivariate polyno- mials on curves, and generalize the “decoding on curve” algorithm from Reed-Muller codes to these lifted codes to provide correcting algorithms with success probability arbitrarily approaching 1. This gives a family of high rate locally correctable codes that is highly sound. Furthermore, we take a deeper look into the method of multiplicities and provide a new con- struction of locally correctable codes of rate approaching 1, which is also a theoretical connection between the multiplicity codes and lifted Reed Solomon Codes. At last, we generalize the concept of traditional local correction to local correction of multiple bits, and present a family of codes which allow multiple bits to be recovered with probability approaching 1 by visiting a small number of locations of the received word, even when a constant fraction of errors exist. Moreover, our codes are of high rate.
URI: http://hdl.handle.net/10356/69693
Fulltext Permission: open
Fulltext Availability: With Fulltext
Appears in Collections:SPMS Theses

Files in This Item:
File Description SizeFormat 
thesis_amendment.pdf494.77 kBAdobe PDFThumbnail
View/Open

Google ScholarTM

Check

Items in DR-NTU are protected by copyright, with all rights reserved, unless otherwise indicated.