In this first chapter, we set the stage for the book by presenting many of its key concepts of the book and stating a number of important theorems that we prove here.

Boolean functions

Definition 1.1 A Boolean function is a function from the hypercube Ωn : = {−1, 1}n into either {−1, 1} or {0, 1}.

Ωn is endowed with the uniform measure ℙ = ℙn = (½δ−1 + ½δ1)⊗n and E denotes the corresponding expectation. Occasionally, Ωn will be endowed with the general product measure but in such cases the p is made explicit. Ep then denotes the corresponding expectation.

An element of Ωn is denoted by either ω or ωn and its n bits by x1, …, xn so that ω = (x1,…, xn).

For the range, we choose to work with {−1, 1} in some contexts and {0, 1} in others, and at some specific places we even relax the Boolean constraint (i.e., that the function takes only two possible values). In these cases (which are clearly identified), we consider instead real-valued functions f: Ωn → ℝ.

A Boolean function f is canonically identified with a subset Af of Ωn via Af : = {ω : f(ω) = 1}.

Remark Often, Boolean functions are defined on {0, 1}n rather than Ωn = {−1, 1}n. This does not make any fundamental difference but, as we see later, the choice of {−1, 1}n turns out to be more convenient when one wishes to apply Fourier analysis on the hypercube.