๐ฎ
๐ฎ
The Ethereal
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
"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 Contributions
Found the code? Know the venue? Think something is wrong? Let us know!
๐ Similar Papers
In the same crypt โ Computational Complexity
๐ฎ
๐ฎ
The Ethereal
An Exponential Separation Between Randomized and Deterministic Complexity in the LOCAL Model
๐ฎ
๐ฎ
The Ethereal
The Parallelism Tradeoff: Limitations of Log-Precision Transformers
๐ฎ
๐ฎ
The Ethereal
The Hardness of Approximation of Euclidean k-means
๐ฎ
๐ฎ
The Ethereal
Slightly Superexponential Parameterized Problems
๐ฎ
๐ฎ
The Ethereal