  The computation of Gr\"obner bases is an established hard problem. By
contrast with many other problems, however, there has been little investigation
of whether this hardness is robust. In this paper, we frame and present results
on the problem of approximate computation of Gr\"obner bases. We show that it
is NP-hard to construct a Gr\"obner basis of the ideal generated by a set of
polynomials, even when the algorithm is allowed to discard a $(1 - \epsilon)$
fraction of the generators, and likewise when the algorithm is allowed to
discard variables (and the generators containing them). Our results shows that
computation of Gr\"obner bases is robustly hard even for simple polynomial
systems (e.g. maximum degree 2, with at most 3 variables per generator). We
conclude by greatly strengthening results for the Strong $c$-Partial Gr\"obner
problem posed by De Loera et al. Our proofs also establish interesting
connections between the robust hardness of Gr\"obner bases and that of SAT
variants and graph-coloring.
