AG 1, MMCI   Info

AG Audience

English

30 Minutes

Saarbrücken

The squared Fourier coefficients of a Boolean function define a probability distribution. The corresponding Shannon entropy is called the Fourier entropy of the Boolean function. 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 is bounded above, up to a constant factor, by the total influence (average sensitivity) of the Boolean function.

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. We also prove the conjecture for some special classes of Boolean functions. Finally, we will conclude with several open questions.

Karl Bringmann

--email hidden

passcode not visible

logged in users only