Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR20-156 | 23rd October 2020 00:09

Codes over integers, and the singularity of random matrices with large entries

RSS-Feed




Revision #1
Authors: Sankeerth Rao Karingula, Shachar Lovett
Accepted on: 23rd October 2020 00:09
Downloads: 83
Keywords: 


Abstract:

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 \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$.



Changes to previous version:

We added a discussion on Woodruff et al's work, as well as a comparison between the two main approaches to study singularity probability of random matrices (LCD vs Fourier).


Paper:

TR20-156 | 22nd October 2020 07:27

Codes over integers, and the singularity of random matrices with large entries


Abstract:

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 \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$.



ISSN 1433-8092 | Imprint