Session II.3 - Real-Number Complexity
Saturday, June 17, 14:30 ~ 15:00
Rigid continuation paths II. 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.
We study the average complexity of solving structured polynomial systems that are characterised by a low evaluation cost, as opposed to the dense random model. Firstly, we design a continuation algorithm that computes, with high probability, an approximate zero of a polynomial system given only as a blackbox 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 $D$ in $n$ variables with only poly$(n,D)L$ operations with high probability. This exceeds the expectations implicit in Smale’s 17th problem.
Joint work with Peter Buergisser (TU Berlin, Germany) and Pierre Lairez (INRIA Saclay, France).