An Exponential Lower Bound for the Permanent of Random Bernoulli Matrix

Source abstract

Let $M_n$ be an $n\times n$ matrix with independent uniform sign entries. We prove that there exist absolute constants $C,c>0$ such that, for all sufficiently large $n$, \[ \mathbb{P}\!\left( \left|\operatorname{Per}(M_n)\right| \ge e^{-Cn}\sqrt{n!} \right) \ge 1-n^{-c}. \] Our proof tracks the total squared permanent of minors under successive row exposure. Up to $k=\lfloor n/2\rfloor$, the total squared permanent grows deterministically via the Boolean lattice up-operator; for larger $k$, the row exposure increments are governed by positive semidefinite Rademacher quadratic forms. Therefore, we confirms the exponential scale lower bound suggested by Tao and Vu.