Events — Colloquia & Seminars
Edge-isoperimetry and Influences
Speaker: Alex Samorodnitsky, Hebrew University & Microsoft Research
Date: Friday, November 21, 2008
Talk: 4:00 PM, 366 WVH
Abstract
We will give alternative proofs of two known results on influences of boolean functions, deriving them from a variant of the edge-isoperimetric inequality on the boolean cube. The first result is a theorem of Kahn, Kalai, and Linial stating that every boolean function has an influential variable. The second result is a theorem of Friedgut which states that a function with a small sum of influences essentially depends only a on few of its variables.
(joint work with Dvir Falik)
Brief Biography
none provided