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 “Fourier-friendly” 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 [...] Computational learning theory is an area of algorithms research devoted to the following task: given a source of “examples” $(x, f(x))$ from an unknown function $f$, compute a “hypothesis” function $h$ which is good at predicting $f(y)$ on future inputs $y$. We will focus on just one possible formulation of the task: [...] A common operation on boolean functions $f : \{-1,1\}^n \to {\mathbb R}$ is restriction to subcubes. Suppose $[n]$ is partitioned into two sets, $J$ and $\overline{J} = [n] \setminus J$. If the inputs bits in $\overline{J}$ are fixed to constants, the result is a function $\{-1,1\}^J \to {\mathbb R}$. For example, if we [...] In this section we treat the domain of a boolean function as ${\mathbb F}_2^n$, an $n$-dimensional vector space over the field ${\mathbb F}_2$. As mentioned earlier, it can be natural to index the Fourier characters $\chi_S : {\mathbb F}_2^n \to \{-1,1\}$ not by subsets $S \subseteq [n]$ but by their $0$-$1$ indicator vectors $\gamma [...] One way a boolean function’s Fourier spectrum can be “simple” is for it to be mostly concentrated at small degree. [...] When there are just $2$ candidates, the majority function possesses all of the mathematical properties that seem desirable in a voting rule (e.g., May’s Theorem and Theorem 32). Unfortunately, as soon as there are $3$ (or more) candidates the problem of social choice becomes much more difficult. For example, suppose we have candidates $a$, [...] |
||||||
|
Copyright © 2013 Ryan O'Donnell -- All Rights Reserved |
||||||
Recent comments