Analysis of Boolean Functions



  • 2017 Autumn/Monsoon (Aug - Dec)

In this course we will explore the Fourier analysis of Boolean functions, f:{0,1}^n→{0,1}. The powerful techniques from this field have application in numerous areas of computer science. We will spend some time developing the area's basic mathematics; however, the main focus will be on applications, in CS theory and beyond. In particular, we will discuss applications to property testing, probabilistically checkable proofs, coding theory, learning, voting theory, social choice. Etc.

Reference: Ryan O'Donnell, "Analysis of Boolean Functions",