CMU online course: Lecture 22 published

The video for Lecture 22 of the online course is available on the course web page.

Chapter 7 notes

The study of property testing was initiated by Rubinfeld and Sudan [RS96] and significantly expanded by Goldreich, Goldwasser, and Ron [GGR98]; the stricter notion of local testability was introduced (in the context of error-correcting codes) by Friedl and Sudan [FS95]. The first local tester for dictatorship was given by Bellare, Goldreich, and Sudan [BGS95,BGS98] (as in Exercise 8); it was later rediscovered by Parnas, Ron, and Samorodnitsky [PRS01,PRS02]. The relevance of Arrow’s Theorem to testing dictatorship was pointed out by Kalai [Kal02].
Continue reading Chapter 7 notes

CMU online course: Lecture 21 published

The video for Lecture 21 of the online course is available on the course web page.

CMU online course: Lecture 20 published

The video for Lecture 20 of the online course is available on the course web page.

Chapter 7 exercises

Continue reading Chapter 7 exercises

CMU online course: Lecture 19 published

The video for Lecture 19 of the online course is available on the course web page.

CMU online course: Lecture 18 published

The video for Lecture 18 of the online course is available on the course web page.

§7.4: Highlight: Håstad’s hardness theorems

In Theorem 36 we saw that it is $\mathsf{NP}$-hard to $(1-\delta_0, 1)$-approximate Max-E$3$Sat for some positive but inexplicit constant $\delta_0$. You might wonder how large $\delta_0$ can be. The natural limit here is $\frac18$ because there is a very simple algorithm which satisfies a $\frac78$-fraction of the constraints in any Max-E$3$Sat instance:
Continue reading §7.4: Highlight: Håstad’s hardness theorems

CMU online course: Lecture 17 published

The video for Lecture 17 of the online course is available on the course web page. It is a guest lecture by John Wright.

CMU online course: Lecture 16 published

The video for Lecture 16 of the online course is available on the course web page.