Polynomial systems solving

This paper improves the complexity analysis given in ‘Refined F5 algorithms for ideals of minors of square matrices’ . A theorem about the structure of grevlex staircases of reverse lexicographic ideals is established, then applied to give an upper bound on the arithmetic complexity of computing Gröbner bases of comaximal minors of square matrices in the zero-dimensional case and under genericity assumptions. A lower bound on the size of a reduced grevlex Gröbner basis of such determinantal systems is also given. Both results depend on the conjectural nonemptiness of an explicit Zariski open subset.

This paper gives a new algorithm to compute Gröbner bases of maximal minors of matrices of polynomials, and applies this algorithm to compute the critical points of a polynomial restricted to an algebraic variety. A complexity analysis of this new algorithm is also given.

This talk was about some extensions of recent results on the complexity of computing Gröbner bases of comaximal determinantal systems and the implications of these results for some multivariate post-quantum cryptography schemes.

This talk was about the joint work in ‘Refined $F_5$ algorithms for ideals of minors of square matrices.’

This talk was about applications of my work to the analysis of multivariate post-quantum cryptography schemes which rely on the hardness of the MinRank problem.

This talk was about some recent work on computing Gröbner bases of determinantal ideals of square matrices.

This paper gives new criteria for the detection and avoidance of reductions to zero when computing Gröbner bases of determinantal ideals of square matrices of polynomials. In the comaximal case and under certain genericity assumptions, all reductions to zero are avoided and a complexity analysis of the resulting algorithm is provided.