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

## CMU online course: Lecture 14 published

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

## Simons Institute semester on Real Analysis in Computer Science

The following message is from Elchanan Mossel at the Simons Institute:

Dear Colleagues,

The Simons Institute for Theory of computing will run a program on Real Analysis in Computer Science during the fall semester of 2013.

Could you help spreading the word around, in particular to young scientists who may be interested to participate in the program as research fellows?

http://simons.berkeley.edu/fellows.html

In the previous section we saw that every subproperty of the dictatorship property has a $3$-query local tester. In this section we will show that any property whatsoever has a $3$-query local tester — if an appropriate “proof” is provided.