Singularity of random integer matrices with large entries

October 22, 2020 ยท The Ethereal ยท ๐Ÿ› International Workshop and International Workshop on Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques

๐Ÿ”ฎ THE ETHEREAL: The Ethereal
Pure theory โ€” exists on a plane beyond code

"No code URL or promise found in abstract"

Evidence collected by the PWNC Scanner

Authors Sankeerth Rao Karingula, Shachar Lovett arXiv ID 2010.12081 Category cs.CC: Computational Complexity Cross-listed cs.DM, cs.IT, math.PR Citations 3 Venue International Workshop and International Workshop on Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques Last Checked 2 months ago
Abstract
We study the singularity probability of random integer matrices. Concretely, the probability that a random $n \times n$ matrix, with integer entries chosen uniformly from $\{-m,\ldots,m\}$, is singular. This problem has been well studied in two regimes: large $n$ and constant $m$; or large $m$ and constant $n$. In this paper, we extend previous techniques to handle the regime where both $n,m$ are large. We show that the probability that such a matrix is singular is $m^{-cn}$ for some absolute constant $c>0$. We also provide some connections of our result to coding theory.
Community shame:
Not yet rated
Community Contributions

Found the code? Know the venue? Think something is wrong? Let us know!

๐Ÿ“œ Similar Papers

In the same crypt โ€” Computational Complexity