epsilon-regular « Analysis of Boolean Functions

Deepak: <a href="http://www.contrib.andrew.cmu.edu/~ryanod/?p=1339#comment-11901" title="On: §8.4: $p$-biased analysis">Cool! That all makes sense.
Ryan O'Donnell: <a href="http://www.contrib.andrew.cmu.edu/~ryanod/?p=1189#comment-11893" title="On: §7.2: Probabilistically checkable proofs of proximity">Thanks on both!
Ryan O'Donnell: <a href="http://www.contrib.andrew.cmu.edu/~ryanod/?p=1339#comment-11892" title="On: §8.4: $p$-biased analysis">1. Fixed, thanks 2. Fixed, thanks 3. For the first two occ...
Avishay Tal: <a href="http://www.contrib.andrew.cmu.edu/~ryanod/?p=1189#comment-11887" title="On: §7.2: Probabilistically checkable proofs of proximity">Two small comments regarding the proof of theorem 16. - In ...
Deepak: <a href="http://www.contrib.andrew.cmu.edu/~ryanod/?p=1339#comment-11869" title="On: §8.4: $p$-biased analysis">A couple of small things: Ex. 42, under equation (2), \pi...
Ryan O'Donnell: <a href="http://www.contrib.andrew.cmu.edu/~ryanod/?p=1323#comment-11822" title="On: §8.3: Orthogonal decomposition">Correct, thanks!
Tim Black: <a href="http://www.contrib.andrew.cmu.edu/~ryanod/?p=1323#comment-11800" title="On: §8.3: Orthogonal decomposition">I think your $j$ should be an $i$ (or vice-versa) in the sen...

§6.1: Notions of pseudorandomness

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).

[...]

Analysis of Boolean Functions

Contents

§6.1: Notions of pseudorandomness

Other Courses

Recent comments