From: Rosa Teorell (rosat@microsoft.com)
Date: Fri Jan 09 2004 - 14:08:42 PST
You are invited to attend...
************************************************************************
*****************************
WHO: Ryan O'Donnell
AFFILIATION: Institute of Advance Studies, School of Mathematics
TITLE: Analysis of Boolean Functions
WHEN: Thu 1/22/2004
WHERE: 113/1159 Research Lecture Room, Microsoft Research
TIME: 10:30AM - 12:00PM
HOST: Jennifer Chayes
************************************************************************
******************************
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?]
BIO:
Ryan O'Donnell received his Bachelor's degree in Mathematics & Computer
Science from the University of Toronto in 1995 and his PhD from the
Mathematics department at MIT in 1999. At MIT he studied theoretical
computer science under the supervision of Madhu Sudan. Ryan is
currently a postdoc at IAS. His achievements include the Best Student
Paper award at the 2002 Conference on Computational Complexity and the
Best Paper award at the 2003 Conference on Computational Complexity.
_______________________________________________
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 : Fri Jan 09 2004 - 14:09:20 PST