Comments for Analysis of Boolean Functions

Comment on §2.1: Social choice functions by Ryan O'Donnell

Ryan O'Donnell — Wed, 09 May 2012 20:26:23 +0000

Fixed, thanks!

Ryan O'Donnell — Wed, 09 May 2012 20:09:42 +0000

Thanks, fixed!

Ryan O'Donnell — Wed, 09 May 2012 20:02:50 +0000

Regarding Prahladh’s good points, I have revamped this section somewhat.

Andy D — Tue, 08 May 2012 17:23:44 +0000

Good stuff!
Quick edit: Below Remark 32, “Recall from Theorem Theorem 2.44″

Hamidreza Jahanjou — Fri, 04 May 2012 18:04:46 +0000

Hi, in definition 6. It seems to me that the recursive majority function should be defined as

Maj_n^{d+1}(x^{(1)}, …, x^{(n)}) = Maj_n(Maj_n^{d}(x^{(1)}), …, Maj_n^{d}(x^{(1)}))

x^{(i)}\in {+1, -1}^n. Am I right?

Ryan O'Donnell — Fri, 04 May 2012 14:36:40 +0000

Thanks yn — of course I meant to link to that, but somehow forgot!

Ryan O'Donnell — Fri, 04 May 2012 14:34:49 +0000

Yep, fixed. Thanks Andy.

yn — Thu, 03 May 2012 13:52:21 +0000

The Impagliazzo, Moore, Russell proof can be found at http://arxiv.org/abs/1205.0263 .

Andy D — Sun, 29 Apr 2012 21:34:34 +0000

Hey Ryan, enjoying your posts; wish I had time to work on these!

Looks like you want a “sgn” in Ex. 1.a.

Ryan O'Donnell — Sat, 28 Apr 2012 19:40:16 +0000

Keep them coming, Alex!