Hilbert's Nullstellensatz and Linear Algebra: An Algorithm for Determining Combinatorial Infeasibility

Systems of polynomial equations can be used to compactly and elegantly model combinatorial problems in such a way that if a given combinatorial property is not satisfied, then the system of polynomial equations has no solution. If a system of polynomial equations has no solution, there exists a very specific algebraic proof of infeasibilty via the famous Hilbert's Nullstellensatz. Using the NulLA algorithm (Nullstellensatz Linear Algebra algorithm), we investigate the form of these algebraic certificates of infeasibility, both in terms of their combinatorial properties and in terms of algorithmic enhancements arising from these certificates. No knowledge of algebraic geometry or prior knowledge of Hilbert's Nullstellensatz is assumed for this talk.

Speaker Bio: Susan Margulies received her Ph.D. in Computer Science from UC Davis in 2008, and promptly jaunted off to Rice University in Houston, Texas and the Computational and Applied Math Department. Five papers, three Matlab classes, and two graph theory classes later, she was off to the Math Department at Penn State University where she did tons of mountain biking in Rothrock State forest. She is now an Assistant Professor in the Math Department at the US Naval Academy, and is just finishing her second year (her ``youngster" year in Navy-speak). Her work on Hilbert's Nullstellensatz was awarded the 2010 Informs Computing Society Prize.

Presentation Slides: PDF

Note: Visitors from outside NIST must contact Cathy Graham; (301) 975-3800; at least 24 hours in advance.