Los Angeles Combinatorics and Complexity Seminar: Complexity of computing zeros of structured polynomial systems

Tuesday, November 10, 2020 at 9:30am to 10:00am

This is a past event.
Virtual Event

Peter Bürgisser, TU Berlin, Germany

Abstract: Can we solve polynomial systems in polynomial time?  This question received different answers in different contexts.  The NP-completeness of deciding the feasibility of a general polynomial system in both Turing and BSS models of computation is certainly an important difficulty but it does not preclude efficient algorithms for computing all the roots of a polynomial system or solving polynomial systems with as many equations as variables, for which the feasibility over algebraically closed fields is granted under genericity hypotheses.  And indeed, there are several ways of computing all $\delta^n$ zeros of a generic polynomial system of $n$
equations of degree $\delta > 1$ in $n$ variables with
$\operatorname{poly}(\delta^n)$ arithmetic operations.

Smale's 17th problem is a clear-cut formulation of the problem in a numerical setting.  It asks for an algorithm, with polynomial average complexity, for computing one  approximate zero of a given polynomial system, where the complexity is to be measured with respect to the dense input size $N$, that is, the number of possible monomials in the input system.

We design a probabilistic algorithm that, on input $\epsilon>0$ and a polynomial   system $F$ given by black-box evaluation functions, outputs an approximate   zero of $F$, in the sense of Smale, with probability at least $(1-\epsilon)$.   When applying this algorithm to $u \cdot F$, where $u$ is uniformly random in   the product of unitary groups, the algorithm performs   $\operatorname{poly}(n, \delta) \cdot L(F) \cdot \left( \Gamma(F) \log \Gamma(F) + \log \log \epsilon^{-1} \right)$   operations on average. Here $n$ is the number of variables, $\delta$ the   maximum degree, $L(F)$ denotes the evaluation cost of $F$, and $\Gamma(F)$   reflects an aspect of the numerical condition of $F$. Moreover, we prove that   for inputs given by random Gaussian algebraic branching programs of   size $\operatorname{poly}(n,\delta)$, the algorithm runs on average in time   polynomial in $n$ and $\delta$. Our result may be interpreted as an   affirmative answer to a refined version of Smale's 17th problem, concerned   with systems of structured polynomial equations.

This is joint work with Felipe Cucker and Pierre Lairez.  The talk will not go into technical details and will be accessible to the general audience.


Dial-In Information

Zoom Meeting: https://ucla.zoom.us/j/96564290758
Meeting ID: 965 6429 0758
Passcode: Please see your email for the passcode to join via Zoom
Warning: You must be registered under your name to be admitted.

Event Type

Lecture / Talk / Workshop

Add this to your calendar

Recent Activity