MAX-3LIN-EQN is a problem in Computational complexity theory where the input is a system of linear equations (modulo 2).
The problem is to find an assignment to the variables that satisfies the maximum number of equations.
It is NP-hard to approximate MAX-3LIN-EQN with ratio (1/2 + δ) for any δ > 0.
IAS/Park City Mathematics Series, 2004 page 108
In proceedings of the 29th ACM STOC, 1-10, 1997