The complexity of solving hard polynomial systems: invariants and applications

In this talk I discuss the general problem of estimating the complexity of solving a system of polynomial equations via Groebner bases methods. This question is motivated by post-quantum cryptography, as estimating the security of certain cryptographic schemes requires estimating the complexity of solving an associated system of non-homogeneous multivariate polynomials. This is typically done by computing or bounding from above algebraic invariants associated to the system, such as the first and last fall degree, the Castelnuovo-Mumford regularity, or the degree of regularity of the system. In the talk, I introduce these invariants and compare them to each other. I also present some estimates that were obtained via this approach.