@book{Tarski1951,
  author = {Alfred Tarski},
  title = {A Decision Method for Elementary Algebra and Geometry},
  edition = {Second},
  publisher = {University of California Press},
  address = {Berkeley},
  year = {1951}
}

@inproceedings{Collins1975,
  author = {George E. Collins},
  title = {Quantifier Elimination for Real Closed Fields by Cylindrical Algebraic Decomposition},
  booktitle = {Automata Theory and Formal Languages},
  editor = {H. Brakhage},
  series = {Lecture Notes in Computer Science},
  volume = {33},
  pages = {134--183},
  publisher = {Springer},
  year = {1975},
  doi = {10.1007/3-540-07407-4_17}
}

@inproceedings{Canny1988,
  author = {John F. Canny},
  title = {Some Algebraic and Geometric Computations in {PSPACE}},
  booktitle = {Proceedings of the Twentieth Annual ACM Symposium on Theory of Computing},
  pages = {460--467},
  publisher = {ACM},
  year = {1988},
  doi = {10.1145/62212.62257}
}

@incollection{SchaeferCardinalMiltzow2026,
  author = {Marcus Schaefer and Jean Cardinal and Tillmann Miltzow},
  title = {The Existential Theory of the Reals as a Complexity Class: A Compendium},
  editor = {J{\'a}nos Pach and G{\'e}za T{\'o}th},
  booktitle = {Courses in Discrete and Computational Geometry},
  series = {Bolyai Society Mathematical Studies},
  volume = {31},
  pages = {167--313},
  publisher = {Springer},
  year = {2026},
  doi = {10.1007/978-3-032-10503-5_5},
  eprint = {2407.18006},
  archivePrefix = {arXiv}
}

@article{AllenderBurgisserKjeldgaardPedersenMiltersen2009,
  author = {Eric Allender and Peter B{\"u}rgisser and Johan Kjeldgaard-Pedersen and Peter Bro Miltersen},
  title = {On the Complexity of Numerical Analysis},
  journal = {SIAM Journal on Computing},
  volume = {38},
  number = {5},
  pages = {1987--2006},
  year = {2009},
  doi = {10.1137/070697926}
}

@book{BasuPollackRoy2006,
  author = {Saugata Basu and Richard Pollack and Marie-Fran{\c c}oise Roy},
  title = {Algorithms in Real Algebraic Geometry},
  edition = {Second},
  series = {Algorithms and Computation in Mathematics},
  volume = {10},
  publisher = {Springer},
  year = {2006},
  doi = {10.1007/3-540-33099-2}
}

@misc{AndrewsGargSchost2026,
  author = {Robert Andrews and Abhibhav Garg and {\'E}ric Schost},
  title = {Hilbert's {Nullstellensatz} is in the Counting Hierarchy},
  year = {2026},
  eprint = {2602.17904},
  archivePrefix = {arXiv},
  primaryClass = {cs.CC},
  howpublished = {arXiv:2602.17904},
  url = {https://arxiv.org/abs/2602.17904},
  note = {To appear in FOCS 2026}
}

@misc{BalajiShirmohammadiTavenasWorrell2026,
  author = {Nikhil Balaji and Mahsa Shirmohammadi and S{\'e}bastien Tavenas and James Worrell},
  title = {Approximate Polynomial Satisfiability is in the Counting Hierarchy},
  year = {2026},
  eprint = {2610.00644},
  archivePrefix = {arXiv},
  primaryClass = {cs.CC},
  howpublished = {arXiv:2610.00644},
  url = {https://arxiv.org/abs/2610.00644},
  note = {Version 1, September 30, 2026}
}

@article{SchejaStorch1975,
  author = {G{\"u}nter Scheja and Uwe Storch},
  title = {{\"U}ber {Spurfunktionen} bei vollst{\"a}ndigen {Durchschnitten}},
  journal = {Journal f{\"u}r die reine und angewandte Mathematik},
  volume = {278/279},
  pages = {174--190},
  year = {1975},
  doi = {10.1515/crll.1975.278-279.174}
}

@incollection{CattaniDickensteinSturmfels1996,
  author = {Eduardo Cattani and Alicia Dickenstein and Bernd Sturmfels},
  title = {Computing Multidimensional Residues},
  booktitle = {Algorithms in Algebraic Geometry and Applications},
  editor = {Laureano Gonz{\'a}lez-Vega and Tom{\'a}s Recio},
  series = {Progress in Mathematics},
  volume = {143},
  pages = {135--164},
  publisher = {Birkh{\"a}user},
  address = {Basel},
  year = {1996},
  doi = {10.1007/978-3-0348-9104-2_8},
  eprint = {alg-geom/9404011},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/alg-geom/9404011}
}

@incollection{ElkadiMourrain2005,
  author = {Mohamed Elkadi and Bernard Mourrain},
  title = {Symbolic-numeric Methods for Solving Polynomial Equations and Applications},
  booktitle = {Solving Polynomial Equations: Foundations, Algorithms, and Applications},
  editor = {Alicia Dickenstein and Ioannis Z. Emiris},
  series = {Algorithms and Computation in Mathematics},
  volume = {14},
  pages = {125--168},
  publisher = {Springer},
  year = {2005},
  doi = {10.1007/3-540-27357-3_3}
}

@article{BeigelReingoldSpielman1995,
  author = {Richard Beigel and Nick Reingold and Daniel Spielman},
  title = {{PP} Is Closed under Intersection},
  journal = {Journal of Computer and System Sciences},
  volume = {50},
  number = {2},
  pages = {191--202},
  year = {1995},
  doi = {10.1006/jcss.1995.1017}
}

@article{SchaeferStefankovic2025,
  author = {Marcus Schaefer and Daniel {\v S}tefankovi{\v c}},
  title = {Beyond the Existential Theory of the Reals},
  journal = {Theory of Computing Systems},
  volume = {68},
  number = {2},
  pages = {195--226},
  year = {2024},
  doi = {10.1007/s00224-023-10151-x},
  eprint = {2210.00571},
  archivePrefix = {arXiv},
  note = {Revised version arXiv:2210.00571v6, March 3, 2025}
}

@article{Wagner1986,
  author = {Klaus W. Wagner},
  title = {The Complexity of Combinatorial Problems with Succinct Input Representation},
  journal = {Acta Informatica},
  volume = {23},
  number = {3},
  pages = {325--356},
  year = {1986},
  doi = {10.1007/BF00289117}
}

@article{Schwartz1980,
  author = {Jacob T. Schwartz},
  title = {Fast Probabilistic Algorithms for Verification of Polynomial Identities},
  journal = {Journal of the ACM},
  volume = {27},
  number = {4},
  pages = {701--717},
  year = {1980},
  doi = {10.1145/322217.322225}
}

@article{Renegar1992II,
  author = {James Renegar},
  title = {On the Computational Complexity and Geometry of the First-order Theory of the Reals. {II}. {The} General Decision Problem. {Preliminaries} for Quantifier Elimination},
  journal = {Journal of Symbolic Computation},
  volume = {13},
  number = {3},
  pages = {301--327},
  year = {1992},
  doi = {10.1016/S0747-7171(10)80004-5}
}