[1]   Noga Alon: Tools from higher algebra. In Handbook of Combinatorics, volume 2, pp. 1749–1783. MIT Press, 1996. Link at ACM DL.

[2]   László Babai, Anna Gál, and Avi Wigderson: Superpolynomial lower bounds for monotone span programs. Combinatorica, 19(3):301–319, 1999. [doi:10.1007/s004930050058]

[3]   Saugata Basu, Richard Pollack, and Marie-Françoise Roy: Algorithms in Real Algebraic Geometry. Springer, 2006. [doi:10.1007/3-540-33099-2]

[4]    Lenore Blum, Filipe Cucker, Michael Shub, and Steve Smale: Complexity and Real Computation. Springer, 1998. [doi:10.1007/978-1-4612-0701-6]

[5]   Jop Briët, Daniel Dadush, and Sebastian Pokutta: On the existence of 0/1 polytopes with high semidefinite extension complexity. Math. Program., 153(1):179–199, 2015. Preliminary version in ESA’13. [doi:10.1007/s10107-014-0785-x, arXiv:1305.3268]

[6]   Alexander L. Chistov and Dima Grigoriev: Complexity of quantifier elimination in the theory of algebraically closed fields. In Proc. 11th Internat. Symp. Math. Found. Comput. Sci. (MFCS’84), pp. 17–31. Springer, 1984. [doi:10.1007/BFb0030287]

[7]   James H. Davenport and Joos Heintz: Real quantifier elimination is doubly exponential. J. Symbolic Comput., 5(1–2):29–35, 1988. [doi:10.1016/S0747-7171(88)80004-X]

[8]   Samuel Fiorini, Serge Massar, Sebastian Pokutta, Hans Raj Tiwary, and Ronald de Wolf: Exponential lower bounds for polytopes in combinatorial optimization. J. ACM, 62(2/17):95–106, 2015. Preliminary version in STOC’12. [doi:10.1145/2716307]

[9]   Dima Grigoriev: Complexity of deciding Tarski algebra. J. Symbolic Comput., 5(1–2):65–108, 1988. [doi:10.1016/S0747-7171(88)80006-3]

[10]   Joos Heintz: Definability and fast quantifier elimination in algebraically closed fields. Theoret. Comput. Sci., 24(3):239–277, 1983. [doi:10.1016/0304-3975(83)90002-6]

[11]   Pavel Hrubeš and Amir Yehudayoff: Arithmetic complexity in ring extensions. Theory of Computing, 7(8):119–129, 2011. [doi:10.4086/toc.2011.v007a008]

[12]   Douglas John Ierardi: The Complexity of Quantifier Elimination in the Theory of an Algebraically Closed Field. Ph. D. thesis, Cornell University, 1989. Conference version in STOC’89.

[13]   Mauricio Karchmer and Avi Wigderson: On span programs. In Proc. of 8th IEEE Structure in Complexity Theory Conf. (SCT’93), pp. 102–111. IEEE Comp. Soc. Press, 1993. [doi:10.1109/SCT.1993.336536]

[14]   Pascal Koiran: Circuits versus trees in algebraic complexity. In Proc. 17th Symp. Theoretical Aspects of Comp. Sci. (STACS’00), pp. 35–52. Springer, 2000. [doi:10.1007/3-540-46541-3_3]

[15]   Pavel Pudlák and Mateus de Oliveira Oliveira: Representations of monotone Boolean functions by linear programs. ACM Trans. Comput. Theory, 11(4):22:1–22:31, 2019. Preliminary version in CCC’17. [doi:10.1145/3337787, ECCC:TR17-106]

[16]   Julia Robinson: Definability and decision problems in arithmetic. J. Symbolic Logic, 14(2):98–114, 1949. [doi:10.2307/2266510]

[17]   Lajos Rónyai, László Babai, and Murali K. Ganapathy: On the number of zero-patterns of a sequence of polynomials. J. Amer. Math. Soc., 14(3):717–735, 2001. [doi:10.1090/S0894-0347-01-00367-8]

[18]   Thomas Rothvoß: Some 0/1 polytopes need exponential size extended formulations. Math. Program., 142(1):255–268, 2013. [doi:10.1007/s10107-012-0574-3, arXiv:1105.0036]

[19]   Thomas Rothvoss: The matching polytope has exponential extension complexity. J. ACM, 64(6):41:1–41:19, 2017. Preliminary version in STOC’14. [doi:10.1145/3127497, arXiv:1311.2369]

[20]   Amir Shpilka and Amir Yehudayoff: Arithmetic circuits: A survey of recent results and open questions. Found. Trends Theor. Comput. Sci., 5(3–4):207–388, 2010. [doi:10.1561/0400000039]

[21]   Leslie G. Valiant: Reducibility by Algebraic Projections. In Logic and Algorithmic, volume 30 of Monographs of L’Enseignement Mathématique, pp. 365–380. 1982.

[22]   Hugh E. Warren: Lower bounds for approximations by nonlinear manifolds. Trans. Amer. Math. Soc., 133(1):167–178, 1968. [doi:10.2307/1994937]

[23]   Mihalis Yannakakis: Expressing combinatorial optimization problems by linear programs. J. Comput. System Sci., 43(3):441–466, 1991. Preliminary version in STOC’88. [doi:10.1016/0022-0000(91)90024-Y]