Group:Complexity Group
Title: Learning Juntas
Speaker: Kevin Matulef Tsinghua university
Time: 2010-05-05 15:30-2010-05-05 17:00
Venue: FIT 1-222


I will present the paper "Learning Juntas" by Mossel, O'Donnell, and Servedio. In it, the authors give an algorithm for learning juntas (functions that depend on only k out of n relevant variables) from uniform random examples in time roughly n^(k*(??1)) where ?< 2.376 is the best known matrix multiplication exponent. This is the only improvement known over the naive algorithm which takes time roughly n^k.

The crucial arguments in the paper utilize only elementary properties of Fourier analysis of Boolean functions. Those who attended the first week or two of the mini-course should have sufficient background to follow (hopefully!).

Short Bio: