摘要：We consider systems of homogeneous linear equations modulo 2 with three variables in each equation and study balanced assignments as solutions to such equations. We prove that it is hard to distinguish systems where there is a balanced assignment that satisfies a fraction 1−ϵ1−ϵ of the equations from systems where the best balanced assignment satisfies a fraction 12+ϵ12+ϵ of the equations assuming that NP is not contained in quasipolynomial time. This improves on a similar result by Holmerin and Khot who relied on the assumption that NP is not contained in subexponential time. The key for the improvement is to replace long codes used by Holmerin and Khot by the low-degree long code.
关键词：hardness of approximation; inapproximability; probabilistically checkable proofs
