Please use this identifier to cite or link to this item:
Full metadata record
DC FieldValueLanguage
dc.contributor.authorWu, Liyasi
dc.identifier.citationWu, L. (2017). Local correction of codes of high rate. Doctoral thesis, Nanyang Technological University, Singapore.
dc.description.abstractLocally 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.en_US
dc.format.extent97 p.en_US
dc.titleLocal correction of codes of high rateen_US
dc.contributor.supervisorChee Yeow Mengen_US
dc.contributor.supervisorXing Chaopingen_US
dc.contributor.schoolSchool of Physical and Mathematical Sciencesen_US​Doctor of Philosophy (SPMS)en_US
item.fulltextWith Fulltext-
Appears in Collections:SPMS Theses
Files in This Item:
File Description SizeFormat 
thesis_amendment.pdf494.77 kBAdobe PDFThumbnail

Page view(s)

Updated on Jun 20, 2021

Download(s) 50

Updated on Jun 20, 2021

Google ScholarTM




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