期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：2020
卷号：2020
页码：1-19
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：The 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 × n matrix with entries chosen independently from the range {−m, . . . , m}, the probability that it is singular is at most m−cn for some absolute constant c > 0.
