Talks
Fall 2014

On the Critical Point Method and Deciding Connectivity Queries in Real Algebraic Sets: From Theory to Practice

Wednesday, October 15th, 2014 9:00 am10:00 am

The input consists of $s$ polynomials in $n$ variables of degree at most $D$. Usually, the complexity of the algorithms is $(s\, D)^{O(n^\alpha)}$ where $\alpha$ is a constant. In the past decade, tremendous efforts have been deployed to improve the exponents in the complexity bounds. This led to efficient implementations and new geometric procedures for solving polynomial systems over the reals that exploit properties of critical points and the so-called polar varieties.
In the first part of this talk, we present an overview of these techniques and their impact on practical algorithms. In the second part, we show how we can exploit algebraic and geometric properties of polar varieties to improve roadmap algorithms for deciding connectivity queries. In particular, we present an algorithm, obtained with E. Schost, that computes roadmaps in smooth bounded real algebraic sets in time which is essentially $O( (s\, D)^{6(n\log(n))})$. This complexity is subquadratic in the output size and a first implementation shows that it can already solve problems that are out of reach of previous approaches.