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.