[...]
|
||||||
|
In Chapter 1.6 we described the BLR property testing algorithm: given query access to an unknown function $f : \{0,1\}^n \to \{0,1\}$, this algorithm queries $f$ on a few random inputs and approximately determines whether $f$ has the property of being linear over ${\mathbb F}_2$. The field of property testing for boolean functions is concerned [...] In this section we describe some applications of our study of pseudorandomness. [...] In linear algebra there are two equivalent definitions of what it means for a function to be linear: Definition 29 A function $f : {\mathbb F}_2^n \to {\mathbb F}_2$ is linear if either of the following equivalent conditions hold: $f(x+y) = f(x) + f(y)$ for all $x, y \in {\mathbb [...] |
||||||
|
Copyright © 2013 Ryan O'Donnell -- All Rights Reserved |
||||||
Recent comments