The video for Lecture 20 of the online course is available on the course web page.
|
||||||
|
The video for Lecture 19 of the online course is available on the course web page. The video for Lecture 18 of the online course is available on the course web page. 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: The video for Lecture 17 of the online course is available on the course web page. It is a guest lecture by John Wright. The video for Lecture 16 of the online course is available on the course web page. This section is about the computational complexity of constraint satisfaction problems (CSPs), a fertile area of application for analysis of boolean functions. To study it we need to introduce a fair bit of background material; in fact, this section will mainly consist of definitions. The video for Lecture 15 of the online course is available on the course web page. The video for Lecture 14 of the online course is available on the course web page. |
||||||
|
Copyright © 2013 Ryan O'Donnell -- All Rights Reserved |
||||||
Recent comments