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 ---------------------------------------------------------- Visit our home page- <http://www.cs.technion.ac.il/~colloq> --------------------------------------------------------- Technion Math. Net (TECHMATH) Editor: Michael Cwikel <techm@math.technion.ac.il> Announcement from: Hadas Heier <heier@cs.technion.ac.il>