PC Seminar: Some (mostly old) results on Approximability

Abstract: Max-Lin is the problem of, given an over-determined system of linear equations modulo two, find the best solution. In other words to satisfy the maximal number of equations.
An old result says that, for any $\epsilon > 0$, it is NP-hard to approximate this within a factor of $\frac 12 + \epsilon$. In other words it is hard to do significantly better than
picking a random solution. We discuss this result and some related results about other problems like Max-3Sat and basic graph problems. If time permits we will mention some more recent result.

This is a seminar in our seminar series on Probability and Combinatorics (PC).