English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

The computation of Gr\"obner bases is an established hard problem. Bycontrast with many other problems, however, there has been little investigationof whether this hardness is robust. In this paper, we frame and present resultson the problem of approximate computation of Gr\"obner bases. We show that itis NP-hard to construct a Gr\"obner basis of the ideal generated by a set ofpolynomials, even when the algorithm is allowed to discard a $(1 - \epsilon)$fraction of the generators, and likewise when the algorithm is allowed todiscard variables (and the generators containing them). Our results shows thatcomputation of Gr\"obner bases is robustly hard even for simple polynomialsystems (e.g. maximum degree 2, with at most 3 variables per generator). Weconclude by greatly strengthening results for the Strong $c$-Partial Gr\"obnerproblem posed by De Loera et al. Our proofs also establish interestingconnections between the robust hardness of Gr\"obner bases and that of SATvariants and graph-coloring.

On the robust hardness of Gr\"obner basis computation