So the problem has poor complexity: what next?

James Davenport
University of Bath, UK


Some interesting problems have a poor worst-case complexity, but may still be soluble in some, or many, cases. If appropriate, there is ‘fixed-parameter tractability’ as one way of describing the solubility. But in other cases, e.g. SAT-solving, there isn’t necessarily a neat theoretical solution, but powerful practical ideas.
What can we say about problems around real quantifier elimination?

Short bio

James Davenport did a PhD in computer algebra (integration) at Cambridge, then worked at IBM Research on what became Axiom. He also worked at Cambridge, Grenoble and Bath, and has been Hebron & Medlock Professor of Information Technology at Bath since 1986. His Grenoble lecture notes contributed to “Calcul Formel” with Yvonne Siret and Evelyne Tournier, translated into English and Russian. He has been associated with SYNASC since 2019, and was awarded an Honorary Doctorate by UVT in 2019.