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 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. [...] In this section we describe the method of applying random restrictions. This is a very “Fourierfriendly” way of simplifying a boolean function. [...] In this section we study the tribes DNF formulas, which serve as an important examples and counterexamples in analysis of boolean functions. Perhaps the most notable feature of the tribes function is that (for a suitable choice of parameters) it is essentially unbiased and yet all of its influences are quite tiny. [...] Perhaps the commonest way of representing a boolean function $f : \{0,1\}^n \to \{0,1\}$ is by a DNF formula: [...] We close this chapter by briefly describing a topic which is in some sense the “opposite” of learning theory: cryptography. At the highest level, cryptography is concerned with constructing functions which are computationally easy to compute but computationally difficult to invert. Intuitively, think about the task of encrypting secret messages: you would like a [...] 

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