Vortrag
eSeminar: Castelnuovo-Mumford Regularity and the Complexity of Gröbner Basis Algorithms (Master's thesis defense)
Vortrag von Andreia Venzin
Datum: 24.02.21 Zeit: 15.00 - 16.00 Raum:
(**This eSeminar will take place on Zoom, using the same meeting details as previous seminars. If you do not have meeting details, please contact simran.tinani@math.uzh.ch **)
Solving systems of polynomial equations in multiple variables is a classical problem in mathematics. It has applications in many different areas of mathematics, such as multivariate public-key cryptosystems, whose security is based on the hardness of solving polynomial systems. The solutions of such a system can be obtained from the lexicographic Gröbner
basis of the ideal generated by the polynomials of the system. Thus, estimating the complexity of Gröbner basis algorithms is central in tackling this problem. Many Gröbner basis algorithms base the computation on Gaussian elimination of so-called Macaulay matrices. Under certain assumptions the complexity estimation of such algorithms can be done by means of an algebraic invariant called Castelnuovo–Mumford regularity.
However, due to the use of concepts from several different areas of mathematics and a lot of preliminaries, many research papers regarding this topic have a high entry-level, and are not easily accessible to many students even at a master level.
The purpose of this thesis is to collect the background information and give an overview of the different mathematical topics and underlying concepts needed in the theory of Gröbner bases and Castelnuovo–Mumford regularity. Furthermore, we show how to connect the complexity of Gröbner basis algorithms and Castelnuovo–Mumford regularity. Finally, we compare this approach with a similar concept called the degree of regularity that is often used in literature.