Max-Planck-Institut für Informatik
max planck institut
informatik
mpii logo Minerva of the Max Planck Society
 

MPI-INF or MPI-SWS or Local Campus Event Calendar

<< Previous Entry Next Entry >> New Event Entry Edit this Entry Login to DB (to update, delete)
What and Who
Title:Upper bounds on Fourier Entropy
Speaker:Nitin Saurabh
coming from:Charles University Prague
Speakers Bio:
Event Type:AG1 Mittagsseminar (own work)
Visibility:D1, MMCI
We use this to send out email in the morning.
Level:AG Audience
Language:English
Date, Time and Location
Date:Thursday, 17 August 2017
Time:13:00
Duration:30 Minutes
Location:Saarbr├╝cken
Building:E1 4
Room:024
Abstract
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.

Contact
Name(s):Karl Bringmann
Video Broadcast
Video Broadcast:NoTo Location:
Tags, Category, Keywords and additional notes
Note:
Attachments, File(s):

Created:
Karl Bringmann, 07/31/2017 12:26 PM
Last modified:
Uwe Brahm/MPII/DE, 08/17/2017 07:01 AM
  • Karl Bringmann, 08/06/2017 12:24 PM
  • Karl Bringmann, 07/31/2017 12:27 PM
  • Karl Bringmann, 07/31/2017 12:26 PM -- Created document.