In this section we give some constructions of boolean functions with strong pseudorandomness properties.
[...]


In this section we give some constructions of boolean functions with strong pseudorandomness properties. [...] We began our study of boolean functions in Chapter 1.2 by considering their polynomial representations over the real field. In this section we take a brief look at their polynomial representations over the field ${\mathbb F}_2$, with $\mathsf{False}$, $\mathsf{True}$ being represented by $0, 1 \in {\mathbb F}_2$ as usual. Note that in the field ${\mathbb [...] The most obvious spectral property of a truly random function $\boldsymbol{f} : \{1,1\}^n \to \{1,1\}$ is that all of its Fourier coefficients are very small (as we saw in Exercise 5.8). [...] Theorem 14 says that if $f$ is an unbiased linear threshold function $f(x) = \mathrm{sgn}(a_1 x_1 + \cdots + a_n x_n)$ in which all $a_i$’s are “small” then the noise stability $\mathbf{Stab}_\rho[f]$ is at least (roughly) $\frac{2}{\pi} \arcsin \rho$. Rephrasing in terms of noise sensitivity, this means $\mathbf{NS}_\delta[f]$ is at most (roughly) $\tfrac{2}{\pi} \sqrt{\delta} [...] In this section we prove two theorems about the degree$1$ Fourier weight of boolean functions: \[ \mathbf{W}^{1}[f] = \sum_{i=1}^n \widehat{f}(i)^2. \] [...] In this section we will analyze the Fourier coefficients of $\mathrm{Maj}_n$. In fact, we give an explicit formula for them in Theorem 16 below. But most of the time this formula is not too useful; instead, it’s better to understand the Fourier coefficients of $\mathrm{Maj}_n$ asymptotically as $n \to \infty$. [...] Majority is one of the more important functions in boolean analysis and its study motivates the introduction of one of the more important tools: the Central Limit Theorem (CLT). [...] Recall from Chapter 2.1 that a linear threshold function (abbreviated LTF) is a booleanvalued function $f : \{1,1\}^n \to \{1,1\}$ that can be represented as \begin{equation} \label{eqn:genericLTF} f(x) = \mathrm{sgn}(a_0 + a_1 x_1 + \cdots + a_n x_n) \end{equation} for some constants $a_0, a_1, \dots, a_n \in {\mathbb R}$. [...] Having derived strong results about the Fourier spectrum of small DNFs and CNFs, we will now extend to the case of constantdepth circuits. We begin by describing how Håstad applied his Switching Lemma to constantdepth circuits. We then describe some Fouriertheoretic consequences coming from a very early (1989) work in analysis of boolean functions [...] Let’s further investigate how random restrictions can simplify DNF formulas. [...] 

Copyright © 2014 Ryan O'Donnell  All Rights Reserved 
Recent comments