The ${\mathbb F}_2$-polynomial representation of a boolean function $f$ is often called its algebraic normal form. It seems to have first been explicitly introduced by Zhegalkin in 1927 [Zhe27].
[...]
|
||||||
|
[...] Recall that a density $\varphi$ is said to be $\epsilon$-biased if its correlation with every ${\mathbb F}_2$-linear function $f$ is at most $\epsilon$ in magnitude. In the lingo of pseudorandomness, one says that $\varphi$ fools the class of ${\mathbb F}_2$-linear functions: [...] 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. [...] |
||||||
|
Copyright © 2018 Ryan O'Donnell -- All Rights Reserved |
||||||
Recent comments