From: Venkatesan Guruswami (venkat@cs.washington.edu)
Date: Thu Jan 15 2004 - 21:37:32 PST
CSE Theory Seminar
TIME: Friday, Jan 23, 2:30-3:20PM
PLACE: CSE 403
SPEAKER: Ryan O'Donnell
IAS, Princeton
TITLE: Analysis of Boolean Functions
ABSTRACT:
The analysis of boolean functions is an emerging field in theoretical
computer science and harmonic analysis. The basic objects of study are
functions mapping the boolean cube {-1,+1}^n into {-1,+1} or R, where
{-1,+1}^n is endowed with the uniform probability measure and its natural
graph structure. The concepts and ideas involved include Fourier analysis,
the influence of variables, noise sensitivity and average sensitivity, the
Bonami-Beckner inequality, ``juntas,'' log-Sobolev inequalities, and
monotonicity, among others.
In addition to being a mathematically elegant area of study, the analysis of
boolean functions has become as a powerful tool for many important areas of
computer science and combinatorics -- especially in the fields of hardness
of approximation, computational learning theory, coding theory, testing,
isoperimetry, circuit complexity, and complexity theory.
In this talk I will give an introduction to the analysis of boolean
functions, including its history and connections to other fields. I will
then present some of my own work on the subject and its computer science
applications, including the following: new efficient learning algorithms
for DNF and functions of thresholds [Klivans-O-Servedio-02,
Bshouty-Mossel-O-Servedio-03] ; hardness amplification with NP [O-02,
Mossel-O-02a] ; ``error-correcting'' truly random bits [Mossel-O-02b] and a
new isoperimetric result via a reverse Bonami-Beckner inequality
[Mossel-O-Regev-Sudakov-03] ; new views/proofs for the theorems of KKL,
Talagrand, and Friedgut [Kindler-O-0?] ; an intriguing new attack on the
hardness of approximating MAX-CUT [Kindler-Mossel-O-0?].
_______________________________________________
Theory-talks mailing list
Theory-talks@cs.washington.edu
http://mailman.cs.washington.edu/mailman/listinfo/theory-talks
_______________________________________________
Theory-group mailing list
Theory-group@cs.washington.edu
http://mailman.cs.washington.edu/mailman/listinfo/theory-group
This archive was generated by hypermail 2.1.6 : Thu Jan 15 2004 - 21:38:19 PST