(#027) On Fourier-entropy Influence Conjecture - Dr. Nitin Saurabh
Date and Time: 10-04-2021, 19:30 - 21:00 IST
Abstract
Given a Boolean function f : {-1,1}^n -> {-1,1}, define the Fourier distribution to be the distribution on subsets of [n], where each subset S of [n] is sampled with probability equaling square of the Fourier coefficient associated with S, \hat{f}(S)^2. The Fourier Entropy-Influence (FEI) conjecture of Friedgut and Kalai (1996) seeks to relate two fundamental measures associated with the Fourier distribution: does there exist a universal constant C>0 such that H(f) <= C Inf(f), where H(f) is the Shannon entropy of the Fourier distribution of f and Inf(f) is the total influence of f. We will discuss the significance of the conjecture, present the current known bounds on Fourier entropy and also discuss its relationship with Mansour's conjecture.
Prerequisites
There is not much of prerequisites, since I plan to introduce things needed from the basics.
Resources
- Survey on Decision trees by Buhrman and de Wolf (only definitions and examples until page 11; skip randomized & quantum parts).
- Survey on Fourier analysis by de Wolf (only until page 3; just the preliminaries part).