Local correction of codes of high rate

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 compu...

Full description

Saved in:
Bibliographic Details
Main Author: Wu, Liyasi
Other Authors: Chee Yeow Meng
Format: Theses and Dissertations
Language:English
Published: 2017
Subjects:
Online Access:http://hdl.handle.net/10356/69693
Tags: Add Tag
No Tags, Be the first to tag this record!
Institution: Nanyang Technological University
Language: English
id sg-ntu-dr.10356-69693
record_format dspace
spelling sg-ntu-dr.10356-696932023-02-28T23:33:24Z Local correction of codes of high rate Wu, Liyasi Chee Yeow Meng Xing Chaoping School of Physical and Mathematical Sciences DRNTU::Science::Mathematics 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. ​Doctor of Philosophy (SPMS) 2017-03-20T02:46:50Z 2017-03-20T02:46:50Z 2017 Thesis Wu, L. (2017). Local correction of codes of high rate. Doctoral thesis, Nanyang Technological University, Singapore. http://hdl.handle.net/10356/69693 10.32657/10356/69693 en 97 p. application/pdf
institution Nanyang Technological University
building NTU Library
continent Asia
country Singapore
Singapore
content_provider NTU Library
collection DR-NTU
language English
topic DRNTU::Science::Mathematics
spellingShingle DRNTU::Science::Mathematics
Wu, Liyasi
Local correction of codes of high rate
description 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.
author2 Chee Yeow Meng
author_facet Chee Yeow Meng
Wu, Liyasi
format Theses and Dissertations
author Wu, Liyasi
author_sort Wu, Liyasi
title Local correction of codes of high rate
title_short Local correction of codes of high rate
title_full Local correction of codes of high rate
title_fullStr Local correction of codes of high rate
title_full_unstemmed Local correction of codes of high rate
title_sort local correction of codes of high rate
publishDate 2017
url http://hdl.handle.net/10356/69693
_version_ 1759853371347435520