May 17, 2016, 4pm
Gwen Spencer, Smith College
Abstract: It is well known that computing a Grobner Basis* for a general polynomial system is not possible in polynomial time (unless P=NP). What about if the Grobner Basis need not be computed exactly? We explore several models of “Approximate Grobner Basis Computation” that allow an algorithm to selectively ignore some of the polynomials: the algorithm is only responsible for returning a Grobner Basis corresponding to the remaining polynomials. Reducing from a charismatic family of tight hardness-of-approximation results, we 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). Our results hold even for very low-degree polynomial systems that are quite sparse, and even when the algorithm is allowed to choose the lexicographic order based on the input. A byproduct of this work is a novel view of the relationships between the members of a famous family of satisfiability results.
*Little prior exposure to Grobner Basis ideas will be assumed.