# Joos Ulrich Heintz

Joos Ulrich Heintz (27 October 1945 - 3 October 2024) was an Argentinean-Swiss mathematician. He was a professor emeritus at the University of Buenos Aires.

## Biography

Heintz was born on 27 October 1945 in Zürich, Switzerland. After studying Mathematics and Cultural Anthropology at the University of Zurich to undergraduate level, he went on to receive a PhD in mathematics in 1982 under the supervision of Volker Strassen. He performed his habilitation in 1986 at the J.W.von Goethe University in Frankfurt am Main where he also studied Turcology and Sephardic history and culture. He was appointed Privatdozent at the J.W. Goethe university Frankfurt am Main. Until his retirement in 2017, he worked as a Full Professor at the University of Buenos Aires and University of Cantabria/Spain and as a Senior Researcher at the National Council for Scientific and Technological Development (CONICET).

## Research

Heintz worked mainly in algebraic complexity theory, computational algebraic geometry, and semi algebraic geometry. For this purpose, he developed with his collaborators, different mathematical tools, e.g. the Bezout Inequality or the first effective Nullstellensatz in arbitrary characteristic. This allowed him and his collaborators to adapt Kronecker's elimination theory to the complexity requirements of modern computer algebra and to prove that all reasonable geometric (not algebraic) computation problems are solvable in PSPACE. Later, he extended these complexity results to polynomial input systems given by arithmetic circuits. The outcome was a worst case optimal probabilistic elimination algorithm with the ability to recognize “easily solvable” input systems which was later implemented by Grégoire Lecerf. Finally, Heintz and his collaborators demonstrated that under fragile and natural assumptions, the worst case complexity of elimination algorithms is unavoidably exponential, independent of the chosen data structure. He applied his results and methods also to mixed integer optimization and foundations of software engineering.
Furthermore, in the field of linguistics, he identified the morphology and phonology of the Turkish languages as a regular language.
In 1987, Heintz founded the Argentinean research group Noaï Fitchas in Buenos Aires. This group was transformed into the international working group TERA (Turbo Evaluation and Rapid Algorithms) with collaborators from several Argentinean, French, Spanish and German universities and research institutions, such as the University of Buenos Aires, CONICET, University of Nice, École Polytechnique at Paris, Universidad de Cantabria (Spain), and Humboldt University at Berlin. Noaï Fitchas was used as a pseudonym for the Argentinean group and numerous influential papers in Computer Algebra were published in the nineties under this name.
Heintz was a member of the editorial boards of several international journals, including the Foundations of Computational Mathematics, Computational Complexity and Applicable Algebra in Engineering, and Communication and Computing, from which he received three best paper awards.
In 2003, Heintz was awarded the Argentinean Konex Medal of Merit.

## Important publications

* Heintz, Joos (1983). Definability and fast quantifier elimination in algebraically closed fields. Theoretical Computer Science. 24. pp. 239–277. https://doi.org/10.1016/0304-3975(83)90002-6
* Caniglia L., Galligo A., Heintz J. (1989) Some new effectivity bounds in computational geometry. In: Mora T. (eds) Applied Algebra, Algebraic Algorithms and Error-Correcting Codes. AAECC 1988. Lecture Notes in Computer Science, vol 357. Springer, Berlin, Heidelberg Best Paper Award. https://doi.org/10.1007/3-540-51083-4_54
* Bank B, Giusti M., Heintz J., Mbakop G.M. (1997). Polar varieties, real equation solving, and data structures: the hypersurface case. Journal of Complexity 13 (1). pp. 5–27 https://doi.org/10.1006/jcom.1997.0432 1997 Journal of Complexity Best Paper Award
* Giusti M., Heintz J., Morais J.E., Morgenstern J., Pardo L.M. (1998). Straight-line programs in geometric elimination theory. Journal of Pure and Applied Algebra 124 (1-3) (1998) 101-146 https://doi.org/10.1016/S0022-4049(96)00099-0
* Heintz J., Kuijpers B., Rojas Paredes A. (2013). Software Engineering and complexity in effective Algebraic Geometry. Journal of Complexity 29 (1). pp. 92–138 https://doi.org/10.1016/j.jco.2012.04.005 2013 Journal of Complexity Best Paper Award
* Bank B., Giusti M., Heintz J., Lecerf G., Matera G., Solernó G. (2015). Degeneracy Loci and Polynomial Equation Solving. Foundations of Computational Mathematics, 15 (1). pp. 159–184 https://doi.org/10.1007/s10208-014-9214-z