4
$\begingroup$

Is there any lecture note or review paper which gives a self-contained proof of the Linial-Mansour-Nisan theorem?


The exposition of that in Ryan O'Donnel's book seems to use terminology and notation which isn't easy to parse unless one reads many pages before that. Most lecture notes I found only at best mention it in the passing.

$\endgroup$
  • $\begingroup$ I find the original paper readable (ma.huji.ac.il/~ehudf/courses/anal09/LMN.pdf). It is almost self-contained except for Haståd's Switching Lemma which can be considered as classical now and for which you can find numerous resources (his thesis for example). $\endgroup$ – holf Jan 29 '17 at 7:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.