ECCC-Report TR20-156https://eccc.weizmann.ac.il/report/2020/156Comments and Revisions published for TR20-156en-usFri, 23 Oct 2020 00:09:20 +0300
Revision 1
| Codes over integers, and the singularity of random matrices with large entries |
Sankeerth Rao Karingula,
Shachar Lovett
https://eccc.weizmann.ac.il/report/2020/156#revision1The prototypical construction of error correcting codes is based on linear codes over finite fields. In this work, we make first steps in the study of codes defined over integers. We focus on Maximum Distance Separable (MDS) codes, and show that MDS codes with linear rate and distance can be realized over the integers with a constant alphabet size. This is in contrast to the situation over finite fields, where a linear size finite field is needed.
The core of this paper is a new result on the singularity probability of random matrices. We show that for a random $n \times n$ matrix with entries chosen independently from the range $\{-m,\ldots,m\}$, the probability that it is singular is at most $m^{-cn}$ for some absolute constant $c>0$.Fri, 23 Oct 2020 00:09:20 +0300https://eccc.weizmann.ac.il/report/2020/156#revision1
Paper TR20-156
| Codes over integers, and the singularity of random matrices with large entries |
Sankeerth Rao Karingula,
Shachar Lovett
https://eccc.weizmann.ac.il/report/2020/156The prototypical construction of error correcting codes is based on linear codes over finite fields. In this work, we make first steps in the study of codes defined over integers. We focus on Maximum Distance Separable (MDS) codes, and show that MDS codes with linear rate and distance can be realized over the integers with a constant alphabet size. This is in contrast to the situation over finite fields, where a linear size finite field is needed.
The core of this paper is a new result on the singularity probability of random matrices. We show that for a random $n \times n$ matrix with entries chosen independently from the range $\{-m,\ldots,m\}$, the probability that it is singular is at most $m^{-cn}$ for some absolute constant $c>0$.Thu, 22 Oct 2020 08:36:16 +0300https://eccc.weizmann.ac.il/report/2020/156