In this section we will collect some applications of the General Hypercontractivity Theorem, including generalizations of the facts from Section 9.5.
[...]


In this section we will collect some applications of the General Hypercontractivity Theorem, including generalizations of the facts from Section 9.5. [...] 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 [...] Perhaps the most common generalized domain in analysis of boolean functions is the case of the hypercube with “biased” bits. [...] 

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