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 |

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