logo Région Lorraine

Meeting detail

Tenth SMArT meeting -- 28-29 April 2016 -- Loria, Nancy

The SMArT project has been instrumental in the building up of the SC² Coordination and Support Action EU project (H2020-FETOPN-2015-CSA_712689). This meeting is to organize the future of the CSA project it is also the occasion to listen to Prof. James Harold Davenport, from the University of Bath, U.K., leader of the SC² project. He is giving a talk on Friday, April 29th, at 14:00 in room C103 in the Loria Building

The Complexity of Cylindrical Algebraic Decomposition
The complexity of cylindrical algebraic decomposition is generally stated to be doubly exponential in the number of variables, which is surprising as the number of solutions (even complex as well as real) to a polynomial system is only singly exponential. We will explain how this arises, give the two key constructions that demonstrate the doubly-exponential lower bound. We then explain recent research which shows that this is really dependent on the number of variables NOT constrained by equations, which bridges the gap between common sense and the known bounds.


Erika Abraham, Prof. James Harold Davenport, Pascal Fontaine, Stephan Merz, Thomas Sturm.