degree-1 « Analysis of Boolean Functions

Federico Magallanez: <a href="http://www.contrib.andrew.cmu.edu/~ryanod/?p=245#comment-18097" title="On: §1.3: The orthonormal basis of parity functions">Maybe it's just me, but I think it will be helpful to explai...
Magnus Find: <a href="http://www.contrib.andrew.cmu.edu/~ryanod/?p=802#comment-18070" title="On: §4.3: Random restrictions">Reference to 3.21 should probably be 3.22
Noam Lifshitz: <a href="http://www.contrib.andrew.cmu.edu/~ryanod/?p=1612#comment-17999" title="On: Chapter 10 exercises">(I meant the assumption that $w_1+w_2+\cdots+w_m=1$)
Noam Lifshitz: <a href="http://www.contrib.andrew.cmu.edu/~ryanod/?p=1612#comment-17998" title="On: Chapter 10 exercises">In Ex 1. should all the norms in the next line be r? $$\|w_...
Noam Lifshitz: <a href="http://www.contrib.andrew.cmu.edu/~ryanod/?p=1452#comment-17876" title="On: §9.3: $(2,q)$- and $(p,2)$-hypercontractivity for a single bit">In the proof of Thm 18, you said “(exercise)”, a fitting ex...
Dmitry Itsykson: <a href="http://www.contrib.andrew.cmu.edu/~ryanod/?p=589#comment-17875" title="On: §3.5: Highlight: the Goldreich--Levin Algorithm">It seems to me that there is a typo: "\mathcal{B}_{k,S} into...
Noam Lifshitz: <a href="http://www.contrib.andrew.cmu.edu/~ryanod/?p=1501#comment-17581" title="On: Chapter 9 exercises">In the hint in Ex 27, it should be 25(d)(instead of 27(d))...

§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