Chapter 2: Basic concepts and social choice

Albert Atserias: <a href="http://www.contrib.andrew.cmu.edu/~ryanod/?p=1315#comment-11984" title="On: §8.2: Generalized Fourier formulas ">Hi Ryan. Typo: In the proof of Proposition 19, in the expect...
Deepak: <a href="http://www.contrib.andrew.cmu.edu/~ryanod/?p=1339#comment-11901" title="On: §8.4: $p$-biased analysis">Cool! That all makes sense.
Ryan O'Donnell: <a href="http://www.contrib.andrew.cmu.edu/~ryanod/?p=1189#comment-11893" title="On: §7.2: Probabilistically checkable proofs of proximity">Thanks on both!
Ryan O'Donnell: <a href="http://www.contrib.andrew.cmu.edu/~ryanod/?p=1339#comment-11892" title="On: §8.4: $p$-biased analysis">1. Fixed, thanks 2. Fixed, thanks 3. For the first two occ...
Avishay Tal: <a href="http://www.contrib.andrew.cmu.edu/~ryanod/?p=1189#comment-11887" title="On: §7.2: Probabilistically checkable proofs of proximity">Two small comments regarding the proof of theorem 16. - In ...
Deepak: <a href="http://www.contrib.andrew.cmu.edu/~ryanod/?p=1339#comment-11869" title="On: §8.4: $p$-biased analysis">A couple of small things: Ex. 42, under equation (2), \pi...
Ryan O'Donnell: <a href="http://www.contrib.andrew.cmu.edu/~ryanod/?p=1323#comment-11822" title="On: §8.3: Orthogonal decomposition">Correct, thanks!

In this chapter we introduce a number of important basic concepts including influences and noise stability. Many of these concepts are nicely motivated using the the language of social choice. The chapter is concluded with Kalai’s Fourier-based proof of Arrow’s Theorem.