An Exponential Lower Bound for the Permanent of Random Bernoulli Matrix
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}. \] This establishes the exponential scale lower bound suggested by Tao and Vu. The proof bounds the cumulative logarithmic loss of the sum of squared permanents of minors under row exposure.
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2608.26707
curl -X POST /api/v1/records/arxiv/2608.26707/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2608.26707/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'