BARC talk by Susan Margulies

Tuesday, 15 October 2019, Susan Margulies, Associate Professor at the Department of Mathematics at the US Naval Academy, USA, will give a talk on "Hilbert's Nullstellensatz and Linear Algebra: An Algorithm for Determining Combinatorial Infeasibility".

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

Abstract:
Unlike systems of linear equations, systems of multivariate polynomial equations over the complex numbers or finite fields can be compactly used to model combinatorial problems. In this way, a problem is feasible (e.g. a graph is 3-colorable, Hamiltonian, etc.) if and only if a given system of polynomial equations has a solution. Via Hilbert's Nullstellensatz, we generate a sequence of large-scale, sparse linear algebra computations from these non-linear models to describe an algorithm for solving the underlying combinatorial problem. As a byproduct of this algorithm, we produce algebraic certificates of the non-existence of a solution (i.e.,  non-3-colorability, non-Hamiltonicity, or non-existence of an independent set of size k).

In this talk, we present theoretical and experimental results on the size of these sequences, and the complexity of the Hilbert's Nullstellensatz algebraic certificates. For non-3-colorability over a finite field, we utilize this method to successfully solve graph problem instances having thousands of nodes and tens of thousands of edges. We also describe methods of optimizing this method, such as finding alternative forms of the Nullstellensatz, adding carefully-constructed polynomials to the system, branching and exploiting symmetry.

Bio:
Susan Margulies completed her dissertation in Computer Science in 2008 at University of California, Davis. She continued her academic adventures with two post-docs, one at Rice University in the Computation and Applied Math department, and one at Pennsylvania State University in the Math Department. She is a winner of the 2010 INFORMS Computing Society Prize, and was awarded a 2017 Fulbright Scholar Award in conjecture to with Fulbright Austria to teach and research at AAU Klagenfurt in Austria during Spring 2017. She is currently as Associate Professor at the United States Naval Academy in Annapolis, Maryland, and is attempting to learn to sail.