Dan Spielman Publications

We prove that the probability that Gaussian elimination with partial pivoting on n × n random matrices has growth ρ is at least inverse quasi-polynomial: Ω(exp(−c log²(ρ) 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.

Here we provide our solutions to the First Proof questions. We also discuss the best responses from publicly available AI systems that we were able to obtain in our experiments prior to the release of the problems on February 5, 2026. We hope this discussion will help readers with the relevant domain expertise to assess such responses.