Vu's global rank resilience conjecture for Rademacher matrices

Let M{±1}n×mM\in\{\pm1\}^{n\times m} with mnm\geq n, and let Res(M)\operatorname{Res}(M) be the least number of entry-flips needed to produce from MM a matrix whose rank is strictly less than nn. Let MMnM\sim\mathcal{M}_n, where Mn\mathcal{M}_n is the distribution of n×nn\times n Rademacher matrices, whose entries are independent random variables taking the values 1-1 and 11 with probability 1/21/2 each. Vu's global rank resilience conjecture. One has

Res(M)=(1/2+o(1))n\operatorname{Res}(M)=\left(1/2+o(1)\right)n

a.a.s. as nn\to\infty. This strengthens the singularity estimate for random Rademacher matrices: exponential upper bounds on the singularity probability imply only a weaker lower bound of order n/lognn/\log n for the resilience, whereas the conjecture predicts the optimal asymptotic value n/2n/2.

Sources & referencesView supporting material

Primary source

Elad Aigner-Horev, Daniel Rosenberg and Roi Weiss, “Resilience of Rademacher chaos of low degree”, arXiv:2402.10504 (2025).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.