Chapter 8: Generalized domains

So far we have studied functions $f : \{0,1\}^n \to {\mathbb R}$. What about, say, $f : \{0,1,2\}^n \to {\mathbb R}$? In fact, very little of what we’ve done so far depends on the domain being $\{0,1\}^n$; what it has mostly depended on is our viewing the domain as a product probability distribution. Indeed, much [...]

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 [...]

Chapter 7 exercises

[...]

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

[...]

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

[...]

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

[...]

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 [...]

§7.1: Dictator testing

In Chapter 1.6 we described the BLR property testing algorithm: given query access to an unknown function $f : \{0,1\}^n \to \{0,1\}$, this algorithm queries $f$ on a few random inputs and approximately determines whether $f$ has the property of being linear over ${\mathbb F}_2$. The field of property testing for boolean functions is concerned [...]

Chapter 7: Property testing, PCPPs, and CSPs

In this chapter we study several closely intertwined topics: property testing, probabilistically checkable proofs of proximity (PCPPs), and constraint satisfaction problems (CSPs). All of our work will be centred around the task of testing whether an unknown boolean function is a dictator. We begin by extending the BLR Test to give a $3$-query property testing [...]

Chapter 6 notes

The ${\mathbb F}_2$-polynomial representation of a boolean function $f$ is often called its algebraic normal form. It seems to have first been explicitly introduced by Zhegalkin in 1927 [Zhe27].

[...]