Biplanar Crossing Numbers and Random Graphs
Gwen Spencer
Smith College http://www.math.smith.edu/~gspencer/ 

Abstract 
On the Robust Hardness of Grobner Basis Computation
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 NPHard 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 strikinglysimple polynomial systems (sparse, low degree, highly symmetric, etc.). 