Mathematics

We introduce the concept of weak average-case analysis as an attempt toachieve theoretical complexity results that are closer to practical experiencethan those resulting from traditional approaches. The underlying paradigmis accepted in other areas such as non-asymptotic random matrix theoryand compressive sensing, and has a particularly convincing interpretationin the most common situation encountered for condition numbers, where itamounts to replacing a null set of ill-posed inputs by a "numerical null set".We illustrate the usefulness of these notions by considering three settings:(1) condition numbers that are inversely proportional to a distance of ahomogeneous algebraic set of ill-posed inputs; (2) Renegar's condition numberfor conic optimization; (3) the running time of power iteration for computinga leading eigenvector of a Hermitian matrix.  Joint work with Martin Lotz