Technion

Computer Science Colloquium

Time+Place : Tuesday 08/05/2012 14:30 room 337-8 Taub  Bld.
Speaker    : Guy Kindler
Affiliation: The Hebrew University of Jerusalem
Host       : Eldar Fischer
Title      : Functions which are close to being k-local are juntas

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, are 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

----------------------------------------------------------