Varieties of Doubly-Exponential Behaviour in Cylindrical Algebraic Decomposition

Research output: Contribution to journalConference articlepeer-review


It is almost fifty years since cylindrical algebraic decomposition was introduced: it was far better than previous ideas, but the algorithm was doubly exponential in the number of variables. Various mitigations have been developed over the last forty years. But we have known for over thirty years that cylindrical algebraic decomposition has a worst-case lower bound doubly-exponential in the number of quantifier alternations, which in worst case is proportional to the number of variables. This lower bound can describe the degree of the polynomials, or the number of polynomials, or both. This paper explores the reasons for this, and what further developments, theoretical or practical, might be possible.

Original languageEnglish
Pages (from-to)31-40
Number of pages10
JournalCEUR Workshop Proceedings
Publication statusPublished - 20 Aug 2022
Event6th Satisfiability Checking and Symbolic Computation-Square Workshop, SC-Square 2021 - Virtual, Online, USA United States
Duration: 19 Aug 202120 Aug 2021

Bibliographical note

Funding Information:
Thanks to many people, including my students and colleagues at Bath (especially Dr Uncu) and Coventry, and the members of EU H2020-FETOPEN-2016-2017-CSA project 2 (712689). The writing was partially supported by EPSRC grant EP/T015713.


  • Cylindrical Algebraic Decomposition
  • Equational Constraints
  • Quantifier Elimination

ASJC Scopus subject areas

  • Computer Science(all)


Dive into the research topics of 'Varieties of Doubly-Exponential Behaviour in Cylindrical Algebraic Decomposition'. Together they form a unique fingerprint.

Cite this