Archive for the ‘Boolean Functions’ Category

Analysis of Boolean Functions

Sunday, September 23rd, 2012

Analysis of Boolean Functions. Course by Ryan O’Donnell.

The course description:

Boolean functions, f : {0,1}n → {0,1}, are perhaps the most basic object of study in theoretical computer science. They also arise in several other areas of mathematics, including combinatorics (graph theory, extremal combinatorics, additive combinatorics), metric and Banach spaces, statistical physics, and mathematical social choice.

In this course we will study Boolean functions via their Fourier transform and other analytic methods. Highlights will include applications in property testing, social choice, learning theory, circuit complexity, pseudorandomness, constraint satisfaction problems, additive combinatorics, hypercontractivity, Gaussian geometry, random graph theory, and probabilistic invariance principles.

If you look at the slides from Lecture One, 2007, you will see all the things that “boolean function” means across several disciplines.

It should also give you an incentive to keep up with the videos of the 2012 version.