Analysis of Boolean Functions

Repeats every week every Thursday until Thu Apr 18 2013 except Thu Mar 28 2013.

Thursday, February 28, 2013 - 10:00am to 12:00pm

Thursday, March 7, 2013 - 10:00am to 12:00pm

Thursday, March 14, 2013 - 10:00am to 12:00pm

Thursday, March 21, 2013 - 10:00am to 12:00pm

Thursday, April 4, 2013 - 10:00am to 12:00pm

Thursday, April 11, 2013 - 10:00am to 12:00pm

Thursday, April 18, 2013 - 10:00am to 12:00pm

Location:

32-G882* see room schedule below for future meetings

Speaker:

Irit Dinur

Boolean functions, f : {0,1}n → {0,1}, are a basic object of study in theoretical computer science. In this seminar we will study Boolean functions via their Fourier transform and other analytic methods. 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. Highlights will include applications in constraint satisfaction problems, learning theory, circuit complexity, pseudorandomness, additive combinatorics, hypercontractivity, property testing, social choice, Gaussian geometry, random graph theory, and probabilistic invariance principles. *ROOM SCHEDULE FOR MEETINGS: 3/28: No Meeting Spring Break 4/4: G882 (Hewlett) 4/11: G882 (Hewlett) 4/18: G882 (Hewlett)