Back to Boolean Function Analysis
Back to notes

Restriction

50%

Background

• Influence
• Concentration of Fourier spectrum

Overview

Operationally, a restriction is a partial assignment to a boolean function so that the number of variables decreases. Intuitively, this makes the analysis simpler as the restricted function is simpler. Quantitively, we would hope that some properties of the original function, e.g., influence etc., can be preserved after the restriction.

Definition

We say $(J|z)$ is a restriction of boolean function $f$ if $J\subseteq[n]$ and $z\in\Bit^{\card{\bar{J}}}$. Furthermore, we denote $f_{J|z}(x)$ to be the restricted function of $f$ where $x$’s coordinates in $\bar{J}$ are set to $z$.

In many situations, we would let a restriction to be random in the following sense.

We say $(\bfJ|\bz)$ is a $\delta$-random restriction for some $0<\delta<1$ if for each $i\in[n]$, it has probability $\delta$ being picked by $\bfJ$ and then $\bz$ will set the variables in $\bar{\bfJ}$ with equal probability to be $\pm1$.

Useful Fourier analytic results of restriction

After defining restriction and random restriction of boolean functions, it’s natural to start with deriving some useful Fourier analytic results. First, we would like to know the Fourier coefficients of restricted function.

Let $(J|z)$ be a restriction for boolean function $f$. We have for any $S\subseteq J$,

$$\widehat{f_{J|z}}(S) = \sum_{T\subseteq\bar{J}}\widehat{f}(S\cup T)z^T.$$

\begin{align} f_{J|z}(x) &= \sum_{S\subseteq J,T\subseteq\bar{J}}\widehat{f}(S\cup T)x^Sz^T\\
&= \sum_{S\subseteq J}\Big(\sum_{T\subseteq\bar{J}}\widehat{f}(S\cup T)z^T\Big)x^S. \end{align}

Next, let’s compute the Fourier coefficients of restriction with random assignment $\bz$.

Let $(J|\bz)$ be a restriction with random assignment for boolean function $f$. We have for any $S\subseteq J$, $$\mathbb{E}_{\bz}\widehat{f_{J|\bz}}(S) = \widehat{f}(S).$$

This is directly followed by the previous proposition.

Finally, let’s analyze the Fourier coefficients of function with random restriction.

Let $(\bfJ|\bz)$ be a $\delta$-random restriction for boolean function $f$. We have for any $S\subseteq[n]$, $$\mathbb{E}_{\bfJ,\bz}\widehat{f_{\bfJ|\bz}}(S) = \delta^{\card{S}}\widehat{f}(S).$$

\begin{align} \mathbb{E}_{\bfJ,\bz}[\widehat{f_{\bfJ|\bz}}(S)] &= \sum_{J}\mathbb{P}[\bfJ=J]\cdot\mathbb{E}_{\bz}[\widehat{f_{J|\bz}}(S)]\\
&= \sum_{J}\mathbb{P}[\bfJ=J]\cdot\widehat{f}(S)\cdot\mathbf{1}_{S\subseteq J}\\
&= \mathbb{P}[S\subseteq\bfJ]\widehat{f}(S) = \delta^{\card{S}}\widehat{f}(S). \end{align}

Random restriction and DNFs/CNFs

Baby switching lemma

Let $0<\delta<1/3$ and $(\bfJ|\bz)$ be a $\delta$-random restriction. Suppose $f$ is a DNF/CNF of width $w$, then $$\mathbb{P}_{\bfJ,\bz}[f_{\bfJ|\bz}\text{ is not constant}]\leq3\delta w.$$

The proof flow is basically following the Exercise 4.19 of the textbook Here we consider the case where $f$ is a DNF. In the following, we call a restriction $R=(J|z)$ bad if $f_{J|z}$ is not a constant. Thus, our goal is to upper bound the probability of sampling a bad restriction.

• Define a friend for each bad restriction

Let $R=(J|z)$ be a bad restriction. Define \begin{align} i_R &:= \argmin_{i:\text{the value of the $i$th clause of $f_{J|z}$ is unfixed}}i,\\
j_R &:= \argmin_{j:\text{$x_j$ or $\bar{x_j}$ is not fixed in the $i$th clause of $f_{J|z}$}}j. \end{align}

Next, define the friend of $R$ to be the extension of $R$ with setting $x_{j_R}$ in the way that does not falsify the $i_R$th clause. That is, if $x_{j_R}$ (resp. $\bar{x_{j_R}}$) in the the $i_R$th clause, then set $x_{j_R}$ to be true (resp. false). Denote the friend of $R$ as $F(R)$.

• For any restriction $R^*$, it can be the friend of at most $w$ bad restrictions

Suppose $R^*$ is the friend of two distinct bad restrictions $R$ and $R’$, then $i_R=i_{R’}$.

Suppose not, without loss of generality, assume $i_R<i_{R’}$. Observe the following:

• When $x_{j_R}$ being fixed, the $i_R$th clause in $R^*$ must be fixed otherwise $i_{R’}=i_R$, which is a contradiction.
• Also, by the definition of friend, the $i_R$th clause must be fixed to true. Namely, $f_R$ is actually a constant function since $f$ is a DNF.
• As $i_{R}\neq i_{R’}$, the settings of $R’$ and $R^*$ in the $i_R$th clause are the same, i.e., both are true. That is, $f_{R’}$ is also a constant function, which is a contradiction to the assumption that $R’$ is a bad restriction.

With the above three observations, we conclude that $i_R=i_{R’}$.

• For any bad restriction $R$, $\mathbb{P}_{\bfR}[\bfR=R]=\frac{2\delta}{1-\delta}\mathbb{P}_{\bfR}[\bfR=F(R)]$

Suppose $R=(J|z)$, let $R’=(J\backslash{x_{j_R}}|z\backslash{x_{j_R}})$, observe that $$\mathbb{P}_{\bfR}[\bfR=R’] = \frac{\mathbb{P}_{\bfR}[\bfR=R]}{\delta} = \frac{\mathbb{P}_{\bfR}[\bfR=F(R)]}{(1-\delta)/2}.$$

• Finally, combine the above three points, we have \begin{align} \mathbb{P}_{\bfR}[\bfR\text{ is bad}] &= \sum_{R\text{ is bad}}\mathbb{P}_{\bfR}[\bfR=R]\\
As $\delta<1/3$, we have $\frac{2\delta}{1-\delta}\leq3\delta$ and thus the baby switching lemma holds.