# Noon lecture

list of noon lectures ( 2005 | 2006 | 2007 | 2008 | 2009 | 2010 | 2011 | 2012 | 2013 | 2014 | 2015 | 2016 | 2017 | future lectures)

On 24.03.2016 at 12:20 in S6, there is the following noon lecture:

# Upper Bounds on Fourier-Entropy

## Nitin Saurabh

## The Institute of Mathematical Sciences, Chennai

## Abstract

(joint work with Sourav Chakraborty (CMI Chennai), Raghav Kulkarni (CQT, Singapore) and Satya Lokam (MSR, India))

Given a Boolean function f: {-1,+1}^n -> {-1,+1}, its Fourier Entropy is defined to be the shannon entropy of squared Fourier coefficients. 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 paper we give several upper bounds on the Fourier Entropy of Boolean as well as real valued functions. We first give upper bounds on the Fourier Entropy of Boolean functions in terms of several complexity measures that are known to be bigger than the influence. These complexity measures include, among others, the logarithm of the number of

Webmaster: kamweb.mff.cuni.cz Modified: 19. 10. 2010