Codes and Expansions (CodEx) Seminar

Josue Tonelli-Cueto (University of Texas San Antonio / Johns Hopkins University):
Condition Numbers and Probability for Explaining Algorithms

On the one hand, many of our best-performing algorithms do not achieve optimal complexity bounds. On the other hand, the algorithms that achieve the best complexity bounds are not, many times, the best-performing algorithms. How can we explain this discrepancy? In this talk, we present how using condition numbers and probability we can obtain better explanations for the practical performance of algorithms. We showcase this complexity framework in one particular case: Descartes' Solver for real roots of real univariate polynomials.