IMI Interdisciplinary Mathematics InstituteCollege of Arts and Sciences

Biplanar Crossing Numbers and Random Graphs

Gwen Spencer
Smith College

On the Robust Hardness of Grobner Basis Computation

  • Feb. 23, 2018
  • 2:30 p.m.
  • LeConte 312

It is well known that computing a Grobner Basis for a general polynomial system is not possible in polynomial time (unless P=NP). In combinatorial optimization, 40+ years of study have been devoted to understanding classes of problems that can't even be solved approximately in polynomial time. Is Grobner Basis computation this hard? We propose several models of "Approximate Grobner Basis Computation" and prove that these Approximate Grobner Basis Problems are still NP-Hard for lexicographic orders, even when the algorithm can ignore a substantial constant fraction of the polynomial system (our notions of "approximate" are parameterized). These messages about robust hardness hold even for strikingly-simple polynomial systems (sparse, low degree, highly symmetric, etc.).

© Interdisciplinary Mathematics Institute | The University of South Carolina Board of Trustees | Webmaster