BY DIETER VAN MELKEBEEK In the lecture notes for your course "Randomized Methods in Computation" there is a claim that MaxQE (finding an assignment that satisfies as many equations as possible of a given system of quadratic equations over GF(2)) has a polynomial-time approximation algorithm that yields a factor of 1/2. More precisely, page 9 of http://www.wisdom.weizmann.ac.il/~oded/PS/RND/l08.ps states: "The best known poly-time approximation algorithm for MaxQE gives an approximation ratio of 1/2. The algorithm that achieves this ratio (and its analysis) are beyond the scope of this course and are omitted." This would mean that the hardness of approximation result that is proved as a neat application of small-bias generators, is tight. However, the best known approximation algorithm gives a factor of 1/4, and Johan (JACM 2001) showed that 1/4+epsilon is NP-hard. The algorithm that realizes 1/4 is simple: a random assignment satisfies at least a fraction 1/4 of the equations in expectation, and you can derandomize it using the method of conditional expectations. The following is also interesting in the context of small-bias generators. The systems of quadratic equations that the reduction gives on a positive instance, are fully satisfiable. For such systems, Johan (Random/Approx 2011) showed that a factor of 3/8 is tight: 3/8 + epsilon is NP-hard, and 3/8 can be realized by a randomized algorithm in expectation (and with high probability). One way to derandomize the latter algorithm is by using a generator that fools degree-2 polynomials over GF(2), and such a generator can be constructed as the sum of a constant number of independent samples from a small-bias generator (Lovett showed 4 samples is enough, and Viola tightened it to 2).