[Colloq] Colloquium, Friday, Nov. 21 - Alex Samorodnitsky, Hebrew University & Microsoft Research

[Rachel Kalweit]

There will be a talk on Friday November 21, 2008 at 4pm in room 366.


Speaker: Alex Samorodnitsky, Hebrew University & Microsoft Research

TITLE: Edge-isoperimetry and influences

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.

Host: Emanuele Viola