Error message

Seminar
Speaker
Satya Lokam (Microsoft Research, Bangalore)
Date & Time
22 February 2017, 11:30 to 12:30
Venue
Emmy Noether Seminar Room, ICTS Campus, Bangalore
Resources
Abstract

The squared Fourier coefficients of a Boolean function $f$ define a probability distribution. The corresponding Shannon entropy is called the Fourier entropy of the Boolean function $f$. An outstanding open question is a conjecture of Friedgut and Kalai (1996), called the Fourier Entropy Influence (FEI) Conjecture, asserting that the Fourier Entropy of any Boolean function $f$ is bounded above, up to a constant factor, by the total influence (= average sensitivity) of $f$.

In this talk, we will first review the background, motivation, and status of this conjecture. We will then present upper bounds on Fourier entropy in terms of several complexity measures of Boolean functions. Each of these complexity measures is known to be larger than the influence for every Boolean function. We also prove the conjecture for some special classes of Boolean functions. Finally, we will conclude with several open questions.

(Based on joint work with Sourav Chakraborty, Raghav Kulkarni, and Nitin Saurabh)