Colloquium Details
Hilbert's Nullstellensatz and Linear Algebra: An Algorithm for Determining Combinatorial Infeasibility
| Author: | Susan Margulies Penn State University |
|---|---|
| Date: | October 18, 2012 |
| Time: | 15:30 |
| Location: | 220 Deschutes |
| Host: | Andrzej Proskurowski |
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.
This work was awarded the INFORMS Computing Society prize for 2010.
Graduate students are happily advised that no background in algebraic geometry or familiarity with Hilbert's Nullstellensatz is assumed for this talk. All theorems and terms are clearly explained with friendly pictures and examples.
Biography
Susan Margulies is currently a post-doctoral Research Associate in Mathematics Department of Pennsylvania State University. She has held a post-doctoral appointment in Computational and Applied Mathematics Department, Rice University.
She received her BA in Astrophysics and English from UC Berkeley and PhD in Computer Science from UC Davis.
Her research interests are in the areas of Optimization, Graph Theory, Computer Algebra, Complexity Theory, and Quantum Computing.
In 2010 she received INFORMS Computing Society Prize for the research she will present in her talk.