# Fourier Analysis of Boolean Functions under Random Restriction

### Fourier Transform

Consider a function $$f\colon \{0,1\}^n \to \{-1, 1\}$$ on $$n$$ boolean variables. This can be viewed as a transform of a boolean function $$g\colon \{0,1\}^n \to \{0, 1\}$$ by letting $$f(x) = (-1)^{g(x)}$$. For $$\alpha \in\{0,1\}^n$$, define the characteristic function
$\chi_\alpha(x) = (-1)^{\alpha x} = (-1)^{\sum_i \alpha_i x_i}.$
Here $$\alpha$$ can also be viewed as a subset of $$[n]$$, that is $$\{i\colon \alpha_i = 1\}$$.

The Fourier transform of function $$f$$ at $$\alpha$$ is
$\widehat{f}(\alpha) = \frac{1}{2^n} \sum_{x\in \{0,1\}^n} f(x) \chi_\alpha(x).$
That is, $$f$$ can be uniquely decomposed as a linear combination of the characteristic functions
$f(x) = \sum_{\alpha\in \{0,1\}^n} \widehat{f}(\alpha) \chi_\alpha (x).$
Note that the Fourier transform $$\widehat{f}$$ is a function from $$\{0,1\}^n \to \mathbb{R}$$.

Define the degree of $$\widehat{f}$$ to be the size of the largest $$\alpha$$ such that $$\widehat{f}(\alpha) \neq 0$$. If a function is computed by a decision tree of depth $$d$$, then the degree of its Fourier transform is at most $$d$$.

### Restriction

A restriction of a function is to fix a subset of variables by a specific assignment. This can be done in two steps: picking up a subset of variables, and fixing the values of these variables.

Consider function $$f\colon \{0,1\}^n \to \{-1, 1\}$$. Divide the input variables into two disjoint subsets and write $$f(x, y)$$ where $$x$$ has dimension $$m$$ and $$y$$ has dimension $$n-m$$. Then the Fourier coefficients can be written as
$\widehat{f}(\alpha, \beta) = \frac{1}{2^n} \sum_{(x, y)\in \{0,1\}^n} f(x,y) \chi_\alpha(x)\chi_\beta(y).$

For a fixed $$y\in\{0,1\}^{n-m}$$, let $$f_y \equiv f(x,y)$$, which is a boolean function on $$m$$ inputs. Its Fourier transform is
$\widehat{f_y} (\alpha) = \frac{1}{2^m} \sum_{x} f_y (x) \chi_\alpha(x).$

Then we have the following relationship between $$\widehat{f}$$ and $$\widehat{f_y}$$:
$\widehat{f}(\alpha, \beta) = \frac{1}{2^{n-m}} \sum_y \widehat{f_y}(\alpha) \chi_\beta(y),$
and for each fixed $$\alpha$$
$\sum_\beta \widehat{f}(\alpha, \beta)^2 = \frac{1}{2^{n-m}} \sum_y \widehat{f_y}(\alpha)^2.$
Note here we applied the fact that $$\chi_\alpha (x) \chi_\beta (x) = \chi_{\alpha\oplus\beta} (x)$$ and $$\sum_x \chi_\alpha (x) = 0$$ for $$\alpha\neq 0$$.

### Random Restriction on DNFs

A random restriction on a function is done in two steps: first randomly pick up a fraction $$p$$ of input variables, and then randomly assign 0 or 1 to the remaining variables. Hastad’s Switching Lemma says that, under a random restriction, a $$k$$-DNF formula is simplified dramatically with high probability.

Let $$f$$ be a $$k$$-DNF, and $$\rho$$ be a random restriction with parameter $$p$$. Denote by $$f|_\rho$$ the randomly restricted function. Then the probability that the decision tree depth for $$f|_\rho$$ is bigger than $$d$$ is bounded by
$(5pk)^d.$
Note that this bound does not depend on the number of clauses in the formula. This implies that with probability $$1- (5pk)^d$$, the degree of the Fourier transform $$\widehat{f|_\rho}$$ is at most $$d$$. Based on this, next we show that the large Fourier coefficients of the orignial $$k$$-DNF $$f$$ is bounded.

By the above, we have
${\bf Pr}_{\rho} \left[ deg( \widehat{f|_\rho}) > d \right] \leq (5pk)^d.$
This implies
${\bf E}_{\rho} \left[ \sum_{\alpha \colon |\alpha| >d } \widehat{f|_\rho}(\alpha)^2 \right] \leq (5pk)^d.$

We consider the restriction applied in two steps: picking up a random subset $$s$$ of size $$pn$$ and randomly assign value $$y$$ to the remaining variables. Then
${\bf E}_{s} {\bf E}_{y} \left[ \sum_{\alpha \colon |\alpha| >d, \alpha\subseteq s } \widehat{f|_\rho}(\alpha)^2 \right] = {\bf E}_{s} \left[ \sum_{\alpha \colon |\alpha| >d, \alpha\subseteq s } {\bf E}_{y}[ \widehat{f|_\rho}(\alpha)^2 ] \right]$

By the fact that
${\bf E}_{y}[ \widehat{f|_\rho}(\alpha)^2 ] = \sum_\beta \widehat{f}(\alpha,\beta)^2$
we have the above equals
${\bf E}_{s} \left[ \sum_{\alpha \colon |\alpha| >d, \alpha\subseteq s } \sum_\beta \widehat{f}(\alpha,\beta)^2 \right] = \sum_u \widehat{f}(u)^2 {\bf Pr}_{s} [|s\cap u| > d]$

Considering the cases that $$|u| \geq 2d/p$$. By Chernoff bound, we have
${\bf Pr}_{s} [|s\cap u| > d] \geq 1 – \exp(-d/4) \geq 1/2.$

Finally we have
$\sum_{u\colon |u| \geq 2d/p } \widehat{f}(u)^2 \leq 2 \cdot (5pk)^d$

For $$p = 1/10k$$,
$\sum_{u\colon |u| \geq 20kd } \widehat{f}(u)^2 \leq 2 \cdot 2^{-d}$

comments

Tagged with: , ,
Posted in Theory