In this section we describe some applications of our study of pseudorandomness.
[...]


In this section we describe some applications of our study of pseudorandomness. [...] 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). [...] In this chapter we discuss various notions of pseudorandomness for boolean functions; by this we mean properties of a fixed boolean function which are in some way characteristic of randomly chosen functions. We will see some deterministic constructions of pseudorandom probability density functions with small support; these have algorithmic application in the field of derandomization. [...] Chow’s Theorem was proved by independently by Chow [Cho61] and by Tannenbaum [Tan61] in 1961; see also [Elg61]. [...] [...] 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. \] [...] 

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