BIRS Workshop Lecture Videos

Banff International Research Station Logo

BIRS Workshop Lecture Videos

Hilbert's Nullstellensatz, Grobner Bases, and NP-Complete Problems Susan Margulies; Margulies, Susan


Combinatorial problems can be represented elegantly and efficiently by systems of polynomial equations. Those systems are either feasible or infeasible, depending on whether or not the underlying combinatorial property is present or not present. In this general survey talk, we will explore the infeasible polynomial systems and their associated combinatorial Nullstellensatz certificates, and we will also explore the feasible polynomial systems and their associated Grobner bases. Along the way, we will highlight some natural questions that arise and identify specific advantages/disadvantages of these methods. We will also suggest open problems and further research directions whenever possible.

Item Media

Item Citations and Data


Attribution-NonCommercial-NoDerivatives 4.0 International