## 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.

## 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:

## 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.

## §7.3: CSPs and computational complexity

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.
Continue reading §7.3: CSPs and computational complexity

## CMU online course: Lecture 15 published

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