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).