Introduction

We will be analysing functions $f:{\{0,1\}}^n\to \{0,1\}$.

One reason to be interested in these is for theoretical computer science.

A more combinatorial reason is that a function $f:{\{0,1\}}^n\to \{0,1\}$ can be viewed as a function $f:P([n])\to \{0,1\}$, so can be viewed as a set system (a subset of $P([n])$). Set systems are of interest in combinatorics (e.g. Sperner’s Lemma, Kruskal-Katona, etc).

Remarks on differences between this course and additive combinatorics

In additive combinatorics, it is common to study ${𝔽}_2^n$ in a way that is basis-independent. When studying boolean functions, we won’t be working in a basis-independent way.

Slogan: if you have a basis that you care about, then perhaps you are working in the boolean functions world, rather than the additive combinatorics world.