Boolean hypercube ($\{-1,1{\}}^n$)

The Boolean hypercube is the set $\{-1,1{\}}^n$, or equivalently $\{0,1{\}}^n$. Two vertices are adjacent when they differ in exactly one coordinate.

The edge boundary of a vertex set $A$ consists of graph edges with exactly one endpoint in $A$. In a $d$-regular graph,where $e(A)$ counts edges with both endpoints in $A$.

For $A\subseteq \{0,1{\}}^n$,Equivalently, $A$ spans at most $\frac{1}{2}|A|{\log }_2|A|$ cube edges. Induction on the dimension and concavity of binary entropy prove the inequality.

The binary entropy function isIt is concave on $[0,1]$ and satisfies $H_2(x)\ge 2x$ for $0\le x\le 1/2$ by comparison with the chord from $(0,0)$ to $(1/2,1)$.

A Boolean function is a function on a Boolean hypercube, often with codomain $\{-1,1\}$ or $\{0,1\}$.

A Boolean function $f:\{0,1{\}}^n\to \{0,1\}$ is monotone when $x_i\le y_i$ for every $i$ implies $f(x)\le f(y)$.

For $f:\{-1,1{\}}^n\to \mathbb{R}$, the characters ${\chi }_S(x)={\prod }_{i\in S}{x}_i$ form an orthonormal basis, and the Fourier-Walsh expansion is

For $S\subseteq [n]$, the Walsh character on the Boolean hypercube is ${\chi }_S(x)={\prod }_{i\in S}{x}_i$, equivalently $(-1{)}^{{\sum }_{i\in S}{x}_i}$ in the zero-one convention.

Under the $p$-biased product measure ${\mu }_p$ on $\{-1,1{\}}^n$, the coordinates are independent random variables with $\mathbb{P}(x_i=-1)=p$ and $\mathbb{P}(x_i=1)=1-p$. Writing $\mu =1-2p$, $\sigma =2\sqrt{p(1-p)}$, and ${\varphi }_i=(x_i-\mu )/\sigma$, the products ${\varphi }_S={\prod }_{i\in S}{\varphi }_i$ form the $p$-biased Fourier basis.

The $p$-biased Fourier coefficient of $f$ at $S$ is ${\hat{f}}_p(S)={\mathbb{E}}_{{\mu }_p}[f{\varphi }_S]$.

On the unbiased cube, the discrete derivative isFor the p-biased product measure, the normalization factor is $\sigma /2$.

The influence of coordinate $i$ is ${\mathrm{Inf}}_i(f)=\Vert D_{i}f{\Vert }_2^2$. For a Boolean-valued function on the unbiased cube, it is the probability that flipping coordinate $i$ changes the function value.

The total influence is

For the indicator $f$ of a monotone family under a p-biased product measure, the Margulis-Russo formula identifies the derivative of ${\mathbb{E}}_{{\mu }_p}f$ with the suitably normalized total influence of $f$.

The noise operator averages $f(y)$ over a random $y$ correlated with $x$ by $\rho$. It acts diagonally on the Fourier-Walsh transform:

The noise stability is

The linear Fourier weight is $W_1(f)={\sum }_{|S|=1}\hat{f}(S{)}^2$.

A $J$-junta is a function whose value depends only on coordinates indexed by $J$. A $k$-junta depends on at most $k$ coordinates.

If $f:\{-1,1{\}}^n\to \{-1,1\}$ satisfies $\Vert f^{\le k}{\Vert }_2^2\ge 1-\epsilon$, then it has a real-valued $J$-junta approximation $g$ with $\Vert f-g{\Vert }_2^2\le 2\epsilon$ and

For every $\epsilon >0$, a Boolean function $f$ has an $\exp (O(\mathbf{I}(f)/\epsilon ))$-junta approximation with squared $L^2$ error at most $2\epsilon$.

Every Boolean function of degree at most $k$ is a $k{2}^{k-1}$-junta.

A Boolean function $f:\{0,1{\}}^n\to \{0,1\}$ is $(\epsilon ,p,r)$-quasirandom when conditioning any set of at most $r$ coordinates to any values changes its ${\mu }_p$-expectation by at most $\epsilon$.

For every $\epsilon ,p,r,\delta$, there is $T$ such that every Boolean function has a set $J$ with $|J|\le T$ for which a ${\mu }_p$-random restriction on $J$ leaves an $(\epsilon ,p,r)$-quasirandom function with probability at least $1-\delta$.