Optimal Inapproximability of Promise Equations over Finite Groups

Silvia Butti, Alberto Larrauri, Stanislav Živný

A celebrated result of Hastad established that, for any constant $\epsilon >0$, it is NP-hard to find an assignment satisfying a $(1/|G|+\epsilon )$-fraction of the constraints…