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.

Thursday, December 01, 2005

The Unique Games Conjecture

At the recent FOCS conference, Subhash Khot gave a tutorial on the Unique Games Conjecture. You can see the slides of his talk here.