degree-1 « Analysis of Boolean Functions

Ohad Klein: <a href="http://www.contrib.andrew.cmu.edu/~ryanod/?p=917#comment-25069" title="On: Chapter 5 exercises">Are the indexing in (the start of) 7 OK?
Ohad Klein: <a href="http://www.contrib.andrew.cmu.edu/~ryanod/?p=1061#comment-25067" title="On: §6.4: Applications in learning and testing">"learning algorithm running in time in time"
Amir: <a href="http://www.contrib.andrew.cmu.edu/~ryanod/?p=1189#comment-25065" title="On: §7.2: Probabilistically checkable proofs of proximity">In the proof of Theorem 16, and in the equation immediately ...
Ohad Klein: <a href="http://www.contrib.andrew.cmu.edu/~ryanod/?p=1005#comment-25064" title="On: §6.1: Notions of pseudorandomness">In example 6, should "of codimension less than n" be "of pos...
Ohad Klein: <a href="http://www.contrib.andrew.cmu.edu/~ryanod/?p=833#comment-25061" title="On: Chapter 4 exercises">In 15c (18c in the book), I think it should be $\cap_j{V_j}$...
Ohad Klein: <a href="http://www.contrib.andrew.cmu.edu/~ryanod/?p=856#comment-25060" title="On: §5.1: Linear threshold functions and polynomial threshold functions">Bracket typo: In the proof of thm 10 (12 in the book), $sgn(...
Ohad Klein: <a href="http://www.contrib.andrew.cmu.edu/~ryanod/?p=833#comment-25057" title="On: Chapter 4 exercises">Oops, my bad.

§5.4: Degree-1 weight

In this section we prove two theorems about the degree-$1$ Fourier weight of boolean functions: \[ \mathbf{W}^{1}[f] = \sum_{i=1}^n \widehat{f}(i)^2. \]

[...]

Analysis of Boolean Functions

Contents

§5.4: Degree-1 weight

Other Courses

Recent comments