Events for 04/22/2019 from all calendars

Geometry Seminar

Time: 3:00PM - 4:00PM

Location: BLOC 628

Speaker: J. Maurice Rojas, Texas A&M University

Title: Explicit Univariate Polynomials with Optimal Condition Number (after Beltran, et. al.)

Abstract: The complexity of polynomial system solving depends not only on the input polynomials, but also on their distance from a suitable discriminant variety. One measure of this distance is the condition number, and there are now even theorems to estimate it with high probability. A consequence of these results is that "most" polynomial systems are "well-conditioned," meaning that "most" polynomial systems are "easy" to solve. Rigorously stated, this is the content of Lairez's recent solution to Smale's 17th Problem.

However, a vexing question left open was the construction of an explicit family (computable in polynomial-time) of univariate polynomials with low condition number. This is an instance of "finding hay in a haystack": an object occuring with high probability, lacking an explicit construction. We review a recent solution to this problem by Beltran, Etayo, Marzo, and Orega-Cerda, as well as its connection to Smale's 7th Problem on well-spaced points on the unit 2-sphere.