On the singularity probability of random Bernoulli matrices

Authors:
Top Cited Papers
Publisher website
Google Scholar
Abstract
Let n n be a large integer and let M n M_n be a random n × n n \times n matrix whose entries are i.i.d. Bernoulli random variables (each entry is ± 1 \pm 1 with probability 1 / 2 1/2 ). We show that the probability that M n M_n is singular is at most ( 3 / 4 + o ( 1 ) ) n (3/4 +o(1))^n , improving an earlier estimate of Kahn, Komlós and Szemerédi, as well as earlier work by the authors. The key new ingredient is the applications of Freiman-type inverse theorems and other tools from additive combinatorics.

This publication has 12 references indexed in Scilit: