Wednesday, December 07, 2005

Lemma about low-degree influences

On Monday we didn't quite have enough time to show that for any f : {-1,1}^m -> [-1,1], the number of coordinates with C-degree influence on f at least tau is at most C/tau.

The proof is quite literally one line, so I'll post it here.

0 Comments:

Post a Comment

<< Home