# Hard family for degree-$D$ MAX-3LIN

Max 3LIN is the problem where one is given a linear system of equations $$C$$ over $$\mathbb{F}_2$$ with $$3$$ variables per equation, and needs to determine the maximum number of equations that can be satisfied. There cannot be two different equations involving the same $$3$$ variables. Degree-$$D$$ MAX-3LIN has the additional property that each variable appears in at most $$D$$ of the equations.

I would like to know whether there is a family of instances $$C_i$$ for degree-$$D$$ MAX-3LIN (with $$i$$ variables in instance $$C_i$$) where $$\forall c > 0$$, the fraction of all $$2^i$$ possible assignments that satisfy at least $$\frac{1}{2} + \frac{c}{\sqrt{D}}$$ of the equations goes to $$0$$ as $$i$$ goes to infinity.

Note that:

• Under reasonable conjectures, if we replace the quantifier on $$c$$ to $$\exists$$ the statement is true, by a 2001 hardness of approximation result from Trevisan.
• There also exist values of $$c$$ for which there will always be at least one assignment that satisfies $$\frac{1}{2} + \frac{c}{\sqrt{D}}$$, following a 2015 result from Barak et al.