[...]


[...] A decision tree $T$ for $f : \{1,1\}^n \to \{1,1\}$ can be thought of as a deterministic algorithm which, given adaptive query access to the bits of an unknown string $x \in \{1,1\}^n$, outputs $f(x)$. E.g., to describe a natural decision tree for $f = \mathrm{Maj}_3$ in words: “Query $x_1$, then $x_2$. If they [...] The previous section covered the case of $f \in L^2(\Omega^n, \pi^{\otimes n})$ with $\Omega = 2$; there, we saw it could be helpful to look at explicit Fourier bases. When $\Omega \geq 3$ this is often not helpful, especially if the only “operation” on the domain is equality. For example, if $f : \{\mathsf{Red}, [...] Perhaps the most common generalized domain in analysis of boolean functions is the case of the hypercube with “biased” bits. [...] In this section we describe a basisfree kind of “Fourier expansion” for functions on general product domains. We will refer to it as the orthogonal decomposition of $f \in L^2(\Omega^n, \pi^{\otimes n})$ though it goes by several other names in the literature: e.g., Hoeffding, Efron–Stein, or ANOVA decomposition. [...] In this section we will revisit a number of combinatorial/probabilistic notions and show that for functions $f \in L^2(\Omega^n, \pi^{\otimes n})$, these notions have familiar Fourier formulas which don’t depend on the Fourier basis. [...] We will now begin to discuss functions on (finite) product probability spaces. [...] So far we have studied functions $f : \{0,1\}^n \to {\mathbb R}$. What about, say, $f : \{0,1,2\}^n \to {\mathbb R}$? In fact, very little of what we’ve done so far depends on the domain being $\{0,1\}^n$; what it has mostly depended on is our viewing the domain as a product probability distribution. Indeed, much [...] The study of property testing was initiated by Rubinfeld and Sudan [RS96] and significantly expanded by Goldreich, Goldwasser, and Ron [GGR98]; the stricter notion of local testability was introduced (in the context of errorcorrecting codes) by Friedl and Sudan [FS95]. The first local tester for dictatorship was given by Bellare, Goldreich, and Sudan [BGS95,BGS98] (as [...] 

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