Finding Zeros of Low-Complexity Polynomial Systems
DescriptionSmale's 17th problem asks for an algorithm to compute a zero of a complex polynomial system efficiently (that is, in average polynomial time). After several breakthroughs this problem was recently solved with a positive answer. The success of this endeavour (described in the entry `Smale's problems' in Wikipedia) has raised the question of whether a similar result can be obtained for low-complexity polynomials.A low-complexity polynomial is one that can be evaluated with few arithmetic operations (compared with the the number of coefficients needed to write down the polynomial). For instance, the polynomial (1+X) to the power 2^n can be evaluated with n+1 operations. But to write it down we need 2^n+1 coefficients. The goal of this project is to obtain an algorithm, similar in spirit to the ones developed to answer Smale's 17th problem that would compute zeros efficiently, where now the polynomial time bound is not on the number of coefficients of the polynomials in the system but in their evaluation complexity.It goes without saying, this goal will apply only to some families of low-complexity polynomials. As the complexity analysis we pursue is average-case, it will be convenient to select such families to be unitarily invariant.
|Effective start/end date||1/10/21 → …|