BIRS Workshop Lecture Videos
Complexity of Polynomial System Solving Ergur, Alperen
Analysis of condition number for random matrices originated in the works of von Neumann and Turing on complexity of linear system solving. For the case of non-linear algebraic equations (i.e. polynomials), there are two decoupling facts: feasibility of a system of equations over the complex numbers is NP-Hard, and a generic system of polynomials always has the same number of roots (i.e. Bezout number or BKK bound). These facts led to the search for algorithms that solves a generic polynomial system fast, and a notion of condition number arose naturally. The analysis of condition number for random polynomial systems thus became the central ingredient for understanding complexity of polynomial system solving. We present a rather quick survey on condition number analysis over complex numbers (i.e., a survey on the solution of Smale's 17th problem), then pass to the field of real numbers. We hope to finish by presenting our results on condition number analysis of random real polynomial systems. This is joint work with J. Maurice Rojas and Grigoris Paouris.
Item Citations and Data
Attribution-NonCommercial-NoDerivatives 4.0 International