## View abstract

### Session S34 - Symbolic and Numerical Computation with Polynomials

Friday, July 16, 12:00 ~ 12:30 UTC-3

## Rigid homotopy and structured polynomial systems

### Felipe Cucker

#### City University of Hong Kong, Hong Kong   -   This email address is being protected from spambots. You need JavaScript enabled to view it. document.getElementById('cloak36b2d7dd5763a5a0c7e542693317af51').innerHTML = ''; var prefix = '&#109;a' + 'i&#108;' + '&#116;o'; var path = 'hr' + 'ef' + '='; var addy36b2d7dd5763a5a0c7e542693317af51 = 'm&#97;c&#117;ck&#101;r' + '&#64;'; addy36b2d7dd5763a5a0c7e542693317af51 = addy36b2d7dd5763a5a0c7e542693317af51 + 'c&#105;ty&#117;' + '&#46;' + '&#101;d&#117;' + '&#46;' + 'hk'; var addy_text36b2d7dd5763a5a0c7e542693317af51 = 'm&#97;c&#117;ck&#101;r' + '&#64;' + 'c&#105;ty&#117;' + '&#46;' + '&#101;d&#117;' + '&#46;' + 'hk';document.getElementById('cloak36b2d7dd5763a5a0c7e542693317af51').innerHTML += '<a ' + path + '\'' + prefix + ':' + addy36b2d7dd5763a5a0c7e542693317af51 + '\'>'+addy_text36b2d7dd5763a5a0c7e542693317af51+'<\/a>';

This talk deals with the average complexity of solving structured polynomial systems that are characterized by a low evaluation cost, as opposed to the dense random model previously used. Firstly, we design a continuation algorithm that computes, with high probability, an approximate zero of a polynomial system given only as black-box evaluation program. Secondly, we introduce a universal model of random polynomial systems with prescribed evaluation complexity $L$. Combining both, we show that we can compute an approximate zero of a random structured polynomial system with $n$ equations of degree at most $\delta$ in $n$ variables with only poly($n,\delta$)$L$ operations with high probability. This exceeds the expectations implicit in Smale’s 17th problem.

Joint work with Peter Bürgisser (Technische Universität Berlin) and Pierre Lairez (Inria).