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.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.