Randomized Methods in Computation

(2001 Lecture Notes - Errata)

Oded Goldreich

In general, the notes contain several errors. Some of these errors are noted below. Additional entries are welcome...

• On page 9 of Lecture 8 it is stated that "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 statement is wrong on several accounts; most importantly, the problem is NP-hard to approximate to withing any ratio higher than 1/4 [Hastad, JACM 2001], which is tight by the trivial random assignment algorithm. Furthermore, for (fully) satisfiable instances it is NP-hard to find an assignment that satisfies a $p$ fraction of the equations, for any $p > 3/8$, and this is tight (cf., [Hastad, APPROX'11]). [Noted by Dieter van Melkebeek]

Back to Oded Goldreich's homepage.