Joos Heintz
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Joos Heintz has a total of 18 co-authors. Here are the top co-authors by number of shared publications:
- Bernd Bank
Humboldt-Universität zu Berlin
8 shared publications - Marc Giusti
Laboratoire STIX, Ecole Polytechnique, 91128 Palaiseau
7 shared publications - Guillermo Matera
National Council of Science and Technology (CONICET), Buenos Aires, Argentina
6 shared publications - Luis Miguel Pardo
Santander, Spain
5 shared publications - Bart Kuijpers
Databases and Theoretical Computer Science Group, Data Science Institute (DSI), Hasselt University and Transnational University Limburg, 3500 Hasselt, Belgium
4 shared publications - Pablo Solernó
Departamento de Matemática and IMAS Facultad de Ciencias Exactas y Naturales UBA-CONICET Universidad de Buenos Aires Ciudad Universitaria 1428 Buenos Aires Argentina
4 shared publications
Latest Publications
- 1 March 2026
- Published by Springer Nature in Applicable Algebra in Engineering, Communication and Computing
- Vol. 37 (2) , 207-304
A Kronecker algorithm for locally closed sets over a perfect field
- 1 March 2026
- Published by Springer Nature in Applicable Algebra in Engineering, Communication and Computing
- Vol. 37 (2) , 207-304
A Kronecker algorithm for locally closed sets over a perfect field
- Open Access
A Kronecker algorithm for locally closed sets over a perfect field
We develop a probabilistic algorithm of Kronecker type for computing a Kronecker representation of a zero-dimensional linear section of an algebraic variety $V$ defined over a perfect field $k$. The variety $V$ is the Zariski closure of the set of common zeros $\{F_1=0,\ldots,F_r=0,G\not=0\}$ of multivariate polynomials $F_1,\ldots,F_r\in k[X_1,\ldots,X_n]$ outside a prescribed hypersurface $\{G=0\}$. We assume that $F_1,\ldots,F_r$ satisfy natural geometric conditions, such as regularity and radicality, in the local ring $k[X_1,\ldots,X_n]_G$. Our approach combines homotopic deformation techniques with symbolic Newton-Hensel lifting and elimination. We discuss the concept of lifting curves as intermediate geometric objects that enable efficient computation. The complexity of the algorithm is expressed in terms of the degrees and arithmetic size of the input and achieves soft-quadratic complexity in these parameters. We provide detailed complexity analyses for arbitrary perfect fields, as well as for two important cases in computer algebra: finite fields and the field of rational numbers. For each case, we obtain sharp bounds on the size of the base field or required primes.Open AccessA Kronecker algorithm for locally closed sets over a perfect field
We develop a probabilistic algorithm of Kronecker type for computing a Kronecker representation of a zero-dimensional linear section of an algebraic variety $V$ defined over a perfect field $k$. The variety $V$ is the Zariski closure of the set of common zeros $\{F_1=0,\ldots,F_r=0,G\not=0\}$ of multivariate polynomials $F_1,\ldots,F_r\in k[X_1,\ldots,X_n]$ outside a prescribed hypersurface $\{G=0\}$. We assume that $F_1,\ldots,F_r$ satisfy natural geometric conditions, such as regularity and radicality, in the local ring $k[X_1,\ldots,X_n]_G$. Our approach combines homotopic deformation techniques with symbolic Newton-Hensel lifting and elimination. We discuss the concept of lifting curves as intermediate geometric objects that enable efficient computation. The complexity of the algorithm is expressed in terms of the degrees and arithmetic size of the input and achieves soft-quadratic complexity in these parameters. We provide detailed complexity analyses for arbitrary perfect fields, as well as for two important cases in computer algebra: finite fields and the field of rational numbers. For each case, we obtain sharp bounds on the size of the base field or required primes. - Open Access
On Bezout Inequalities for non-homogeneous Polynomial Ideals
We introduce a "workable" notion of degree for non-homogeneous polynomial ideals and formulate and prove ideal theoretic B\'ezout Inequalities for the sum of two ideals in terms of this notion of degree and the degree of generators. We compute probabilistically the degree of an equidimensional ideal.
Open AccessOn Bezout Inequalities for non-homogeneous Polynomial Ideals
We introduce a "workable" notion of degree for non-homogeneous polynomial ideals and formulate and prove ideal theoretic B\'ezout Inequalities for the sum of two ideals in terms of this notion of degree and the degree of generators. We compute probabilistically the degree of an equidimensional ideal.
- 1 June 2016
- Published by Elsevier in Journal of Complexity
- Vol. 34, 1-29
Quiz games as a model for information hiding
- 1 June 2016
- Published by Elsevier in Journal of Complexity
- Vol. 34, 1-29
Quiz games as a model for information hiding
- 23 October 2014
- Published by Springer Nature in Foundations of Computational Mathematics
- Vol. 15 (1) , 159-184
Degeneracy Loci and Polynomial Equation Solving
- 23 October 2014
- Published by Springer Nature in Foundations of Computational Mathematics
- Vol. 15 (1) , 159-184
Degeneracy Loci and Polynomial Equation Solving
- Open Access
Intrinsic complexity estimates in polynomial optimization
It is known that point searching in basic semialgebraic sets and the search for globally minimal points in polynomial optimization tasks can be carried out using $(s\,d)^{O(n)}$ arithmetic operations, where $n$ and $s$ are the numbers of variables and constraints and $d$ is the maximal degree of the polynomials involved.\spar \noindent We associate to each of these problems an intrinsic system degree which becomes in worst case of order $(n\,d)^{O(n)}$ and which measures the intrinsic complexity of the task under consideration.\spar \noindent We design non-uniformly deterministic or uniformly probabilistic algorithms of intrinsic, quasi-polynomial complexity which solve these problems.Open AccessIntrinsic complexity estimates in polynomial optimization
It is known that point searching in basic semialgebraic sets and the search for globally minimal points in polynomial optimization tasks can be carried out using $(s\,d)^{O(n)}$ arithmetic operations, where $n$ and $s$ are the numbers of variables and constraints and $d$ is the maximal degree of the polynomials involved.\spar \noindent We associate to each of these problems an intrinsic system degree which becomes in worst case of order $(n\,d)^{O(n)}$ and which measures the intrinsic complexity of the task under consideration.\spar \noindent We design non-uniformly deterministic or uniformly probabilistic algorithms of intrinsic, quasi-polynomial complexity which solve these problems. - Open Access
Degeneracy loci and polynomial equation solving
Let V be a smooth equidimensional quasi-affine variety of dimension r over the complex numbers $C$ and let $F$ be a $(p\times s)$-matrix of coordinate functions of $C[V]$, where $s\ge p+r$. The pair $(V,F)$ determines a vector bundle $E$ of rank $s-p$ over $W:=\{x\in V:\mathrm{rk} F(x)=p\}$. We associate with $(V,F)$ a descending chain of degeneracy loci of E (the generic polar varieties of $V$ represent a typical example of this situation). The maximal degree of these degeneracy loci constitutes the essential ingredient for the uniform, bounded error probabilistic pseudo-polynomial time algorithm which we are going to design and which solves a series of computational elimination problems that can be formulated in this framework. We describe applications to polynomial equation solving over the reals and to the computation of a generic fiber of a dominant endomorphism of an affine space.Open AccessDegeneracy loci and polynomial equation solving
Let V be a smooth equidimensional quasi-affine variety of dimension r over the complex numbers $C$ and let $F$ be a $(p\times s)$-matrix of coordinate functions of $C[V]$, where $s\ge p+r$. The pair $(V,F)$ determines a vector bundle $E$ of rank $s-p$ over $W:=\{x\in V:\mathrm{rk} F(x)=p\}$. We associate with $(V,F)$ a descending chain of degeneracy loci of E (the generic polar varieties of $V$ represent a typical example of this situation). The maximal degree of these degeneracy loci constitutes the essential ingredient for the uniform, bounded error probabilistic pseudo-polynomial time algorithm which we are going to design and which solves a series of computational elimination problems that can be formulated in this framework. We describe applications to polynomial equation solving over the reals and to the computation of a generic fiber of a dominant endomorphism of an affine space. - Open Access
- 31 October 2013
- Published by American Mathematical Society (AMS) in Mathematics of Computation
- Vol. 83 (286) , 873-897
Point searching in real singularcomplete intersection varieties: algorithms of intrinsic complexity
Let <!-- MATH $X_1,\ldots ,X_n$ --> be indeterminates over <!-- MATH $\mathbb{Q}$ --> and let <!-- MATH $X:=(X_1,\ldots ,$ --> . Let <!-- MATH $F_1,\ldots ,F_p$ --> be a regular sequence of polynomials in <!-- MATH $\mathbb{Q}[X]$ --> of degree at most such that for each <!-- MATH $1\le k \le p$ --> the ideal <!-- MATH $(F_1,\ldots , F_k)$ --> is radical. Suppose that the variables <!-- MATH $X_1,\ldots ,X_n$ --> are in generic position with respect to <!-- MATH $F_1,\ldots ,F_p$ --> . Further, suppose that the polynomials are given by an essentially division-free circuit in <!-- MATH $\mathbb{Q}[X]$ --> of size and non-scalar depth .- 31 October 2013
- Published by American Mathematical Society (AMS) in Mathematics of Computation
- Vol. 83 (286) , 873-897
Open AccessPoint searching in real singularcomplete intersection varieties: algorithms of intrinsic complexity
Let <!-- MATH $X_1,\ldots ,X_n$ --> be indeterminates over <!-- MATH $\mathbb{Q}$ --> and let <!-- MATH $X:=(X_1,\ldots ,$ --> . Let <!-- MATH $F_1,\ldots ,F_p$ --> be a regular sequence of polynomials in <!-- MATH $\mathbb{Q}[X]$ --> of degree at most such that for each <!-- MATH $1\le k \le p$ --> the ideal <!-- MATH $(F_1,\ldots , F_k)$ --> is radical. Suppose that the variables <!-- MATH $X_1,\ldots ,X_n$ --> are in generic position with respect to <!-- MATH $F_1,\ldots ,F_p$ --> . Further, suppose that the polynomials are given by an essentially division-free circuit in <!-- MATH $\mathbb{Q}[X]$ --> of size and non-scalar depth . - 15 August 2012
- Published by Springer Nature in Applicable Algebra in Engineering, Communication and Computing
- Vol. 23 (3-4) , 179-193
Evaluating geometric queries using few arithmetic operations
- 15 August 2012
- Published by Springer Nature in Applicable Algebra in Engineering, Communication and Computing
- Vol. 23 (3-4) , 179-193
Evaluating geometric queries using few arithmetic operations
- Open Access
On the intrinsic complexity of elimination problems in effective Algebraic Geometry
The representation of polynomials by arithmetic circuits evaluating them is an alternative data structure which allowed considerable progress in polynomial equation solving in the last fifteen years. We present a circuit based computation model which captures all known symbolic elimination algorithms in effective algebraic geometry and show the intrinsically exponential complexity character of elimination in this complexity model.
Open AccessOn the intrinsic complexity of elimination problems in effective Algebraic Geometry
The representation of polynomials by arithmetic circuits evaluating them is an alternative data structure which allowed considerable progress in polynomial equation solving in the last fifteen years. We present a circuit based computation model which captures all known symbolic elimination algorithms in effective algebraic geometry and show the intrinsically exponential complexity character of elimination in this complexity model.