1 Search Results for "Karingula, Sankeerth Rao"


Document
RANDOM
Singularity of Random Integer Matrices with Large Entries

Authors: Sankeerth Rao Karingula and Shachar Lovett

Published in: LIPIcs, Volume 207, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021)


Abstract
We study the singularity probability of random integer matrices. Concretely, the probability that a random n × n matrix, with integer entries chosen uniformly from {-m,…,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.

Cite as

Sankeerth Rao Karingula and Shachar Lovett. Singularity of Random Integer Matrices with Large Entries. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 207, pp. 33:1-33:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)


Copy BibTex To Clipboard

@InProceedings{karingula_et_al:LIPIcs.APPROX/RANDOM.2021.33,
  author =	{Karingula, Sankeerth Rao and Lovett, Shachar},
  title =	{{Singularity of Random Integer Matrices with Large Entries}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021)},
  pages =	{33:1--33:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-207-5},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{207},
  editor =	{Wootters, Mary and Sanit\`{a}, Laura},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2021.33},
  URN =		{urn:nbn:de:0030-drops-147260},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2021.33},
  annote =	{Keywords: Coding Theory, Random matrix theory, Singularity probability MDS codes, Error correction codes, Littlewood Offord, Fourier Analysis}
}
  • Refine by Author
  • 1 Karingula, Sankeerth Rao
  • 1 Lovett, Shachar

  • Refine by Classification
  • 1 Theory of computation → Randomness, geometry and discrete structures

  • Refine by Keyword
  • 1 Coding Theory
  • 1 Error correction codes
  • 1 Fourier Analysis
  • 1 Littlewood Offord
  • 1 Random matrix theory
  • Show More...

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2021

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail