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

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

Yours,
Elchanan Mossel

## §7.2: Probabilistically checkable proofs of proximity

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.
Continue reading §7.2: Probabilistically checkable proofs of proximity

## Additive Combinatorics and the Polynomial Freiman–Rusza Conjecture

I originally planned for Chapter 9 of the book to be about additive combinatorics. However in the interests of completing the book before I die of old age, I am planning to make some cuts. It now looks like Chapter 9 (being a rather standalone topic in the context of the book) will hit the cutting room floor. Drafts of some parts of it are already written, and I decided to publish here a “deleted scene” — the Quasipolynomial Freiman–Ruzsa Theorem highlight. It seemed timely to me in light of several other very nice surveys/expositions/extensions that have appeared recently. Shachar Lovett has posted one survey here, and Eli Ben-Sasson, Noga Ron-Zewi, Madhur Tulsiani, and Julia Wolf have just posted a paper on the topic. Also, Sanders himself has a 1.5-page proof of his result in ${\mathbb F}_2^n$ in a manuscript called On the Bogolyubov–Ruzsa Lemma in ${\mathbb F}_2^n$; I don’t know if it’s appeared anywhere, but I’m sure he’ll send you a copy if you ask nicely

Below is the draft of what was to appear in the book on this topic. I would like to emphasize that its interpretation/proof of the Croot–Sisask result is based on joint discussions with Eric Blais and Shachar Lovett.