Pierre Lairez

Chargé de recherche

Équipe Specfun

email
INRIA Saclay Île-de-France, Bât. Alan Turing
1 rue Honoré d'Estienne d'Orves
Campus de l'École polytechnique
91120 Palaiseau
France
location
48.7146, 2.2056
map
phone
(0033) 01 77 57 80 36
office
1155
gpg public key

## Latest work

### Average analysis of structured polynomial system solving

2020

In “Rigid continuation paths II”, we develop an algorithm to compute an approximate zero of a polynomial system given as a black-box evaluation function. It follows the main lines of the algorithm from Part I but with a probabilistic estimation of the step length for the numerical continuation.

Going a step further, we show that, on average, the algorithm behaves well on a universal family of polynomial system with low evaluation cost. More precisely, we introduce the model of Gaussian random algebraic branching program and show that our algorithm performs $\operatorname{poly}(n, \delta)$ operations on average to solve a random ABP in $n$ variables, of degree $\delta$ and of size $\operatorname{poly}(n, \delta)$.