Time+Place: Tuesday 08/05/2012 14:30 Room 337-8 Taub Bld. Title: Functions which are close to being k-local are juntas Speaker: Guy Kindler http://www.cs.huji.ac.il/~gkindler/ Affiliation: The Hebrew University of Jerusalem Host: Eldar Fischer

Abstract:


Consider a Boolean valued function f over the discrete cube {-1,1}^n.
We say that it is k-local if it is a sum of functions each of which depends
on at most k coordinates. In 2002, Bourgain proved that if f is close to a
k-local function beyond a certain threshold (around 1/\sqrt k), then in fact
f is close to a junta, namely to a function that simply depends on a fixed
number of coordinates depending only on k. Bourgain's result, and others
like it, is useful in many areas of theoretical computer science.

In my talk I'll describe a proof of the same result, with improved
parameters, which goes through functions over Gaussian space rather than the
discrete cube. Our result is considerably simpler than Bourgain's original
proof.

Joint work with Ryan O'Donnell.

No nonstandard prior knowledge will be assumed.

Short Bio:
Graduated from Tel Aviv University, completed Post-Docs in DIMACS,
The Institute For Advanced Study, Microsoft Research, and Weizmann.
Is a senior Lecturer in the Hebrew University.

Refreshments served from 14:15 on,
Lecture starts at 14:30