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.
