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].
[...]


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 © 2015 Ryan O'Donnell  All Rights Reserved 
Recent comments