Johan Håstad: Some parts of “Some optimal inapproximability results”

On popular demand, Johan Håstad has promised to tell us about the paper that was awarded the Gödel Prize last year. In particular, he will focus on his result concerning how hard it is to find good approximate solutions to systems of linear equations.

Suppose that you have a system of equations x + y + z = ODD; x + z + w = EVEN; y + z + w = EVEN; et cetera, where you want to choose integer values (0 or 1 without loss of generality) so that as many equations as possible are satisfied. Perhaps the most naive solution you could think of is to simply assign random values to the variables, and it is not hard to see that this will satisfy 50% of the equations. Surprisingly, it turns out that this naive solution is also optimal --- there is nothing better you can do unless P is equal to NP!

This result is established using so-called probabilistically checkable proofs (PCPs), which have the amazing property that you can check the validity of such proofs just by making a few random spot checks. The famous PCP theorem says that you can code solutions to NP-complete problems in such a way that only a constant number of bits need to be read in order to verify them (with high probability). This theorem will be explained in more detail (but not proven) during the presentation.

This will be a fully self-contained lunch seminar, and no prior knowledge of the subject is assumed. We meet for a light lunch at 12:00 noon sharp. The presentation will start at 12:15 pm and last for 45-60 minutes. If there is interest, there will be a possibility to reconvene after a break and go into more details during 90-120 additional minutes of more technical discussions.

Please sign up for food before Wednesday October 24th, by filling in the following Doodle: www.doodle.com/kceg7yyx7vx8d66y If you have special requirements on the food, you can write that in the comments field.