Coding in theoretical computer science

• Main Author: Chen, Yuan
• Other Authors: Xing Chaoping
• Format: Theses and Dissertations
• Language: English
• Published: 2018
• Subjects: DRNTU::Science::Mathematics::Discrete mathematics::Cryptography; DRNTU::Engineering::Computer science and engineering::Data::Coding and information theory; DRNTU::Science::Mathematics::Discrete mathematics::Combinatorics
• Online Access: http://hdl.handle.net/10356/73170
• Institution: Nanyang Technological University

This thesis contains three topics, list decoding of rank-metric codes, local decoding of Reed-Muller codes and the design of tampering detection codes and its generalization non-malleable codes. The first two topics are the central problems in theoretical computer science and the last one has cryptographic background. They are all focused on the design or decoding of codes with certain properties. In the first topic, we present an explicit construction of rank-metric codes with constant ratio. Such codes are list decoded beyond unique decoding radius which answers an open problem in~\cite{Guru2015}. The ratio of our rank-metric codes can reach $1/2$. Our construction can be seen as a step toward the list decoding of square rank metric codes. These results appear in Chapter 2. In Chapter 3, we further develop a combinatorial tool contributed to this issue, namely subspace design set. Our result can be treated as a generalization of the construction in~\cite{Guru2013B}. In the second topic, we design an local decoding algorithm of Reed-Muller codes based on algebraic geometry codes. The traditional local decoding algorithm of Reed-Muller codes are based on the line decoding, i.e., the decoding of Reed-Solomon codes. If we want to recover multiple points, we have to run this line decoding multiple rounds. To overcome this drawback, we propose a curve decoding via algebraic geometry codes. Our local decoding algorithm can recover as many points as possible in one round. Moreover, our algorithm outperforms the previous local decoding algorithm in both the error probability and query length. %Based on this local decoding algorithm, we present a local list-decoder of Reed-Muller codes. Our local list-decoder runs in sub-linear time in code length and list decode Reed-Muller codes up to the radius $1-\sqrt{\frac{2d}{q}}$. Our result improves the best known local list-decoder over large field~\cite{STV2001}. %All these results can be found in Chapter 4. In our last topic, we focus on the design of tampering detection codes or non-malleable codes resistant to large families of tampering function. Our first result answers the open problem in~\cite{CPX15} by constructing asymptotic optimal systematic Algebraic Manipulation Detection codes. Our second result yields optimal-rate tampering detection codes resistant to the family of linearized polynomials with certain degree. Both of the results are included in Chapter 5. In Chapter 6, we design a class of linear-time encoding and decoding non-malleable codes which is resistant to the family of bit-wise tampering and permutation functions. Our codes extend the non-malleable codes in~\cite{CDD16} which are only resistant to the family of bit-wise tampering functions.