Erik Aas: Boolean influence
Erik Aas, KTH
Time: Mon 2013-02-04 12.10 - 13.00
Location: Room 4523, Lindstedtsvägen 5, 5th floor, KTH CSC
Lunch is served at 12:00 noon (register at doodle.com/yd8uez9idrvba4wp by Thu Jan 31 at 8 pm). Those of us who wish reconvene after a short break for ca two hours of more technical discussions.
Abstract
The influence of a variable of a boolean function is a measure of how likely that variable is to control the output of the function. I'll present some fundamental results concerning the influences of threshold functions (a special kind of boolean function). If time permits we will prove the Kahn-Kalai-Linial theorem, giving a lower bound for the largest influence of a variable of a "balanced" boolean function.