Large Growth Happens: Gaussian Elimination with Partial Pivoting on Random Matrices
We prove that the probability that Gaussian elimination with partial pivoting on $n \times n$ random matrices has growth $ρ$ is at least inverse quasi-polynomial: $Ω(\exp(-c \log^2 (ρ)\log(n)))$ for some constant $c > 0$. This lower bound breaks standard conjectures in the smoothed and average-case analysis of Gaussian elimination. To the best of our knowledge, it is the first non-trivial lower bound on the probability of large growth for Gaussian random matrices.
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2610.08701
curl -X POST /api/v1/records/arxiv/2610.08701/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2610.08701/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'