Seminar: Computer Science for Mathematicians (CMSA)
Date: Tuesday, Oct 20
Time: 11:30 am
Zoom link: https://harvard.zoom.us/j/98231541450
passcode: cmsa
Speaker: Rani Hod (Tel Aviv University)
Title: Improved Lower Bounds for the Fourier Entropy/Influence Conjecture via Lexicographic Functions
Abstract:
Every Boolean function can be uniquely represented as a multilinear polynomial. The entropy and the total influence are two ways to measure the concentration of its Fourier coefficients, namely the monomial coefficients in this representation: the entropy roughly measures their spread, while the total influence measures their average level. The Fourier Entropy/Influence conjecture of Friedgut and Kalai from 1996 states that the entropy to influence ratio is bounded by a universal constant C.
Using lexicographic Boolean functions, we present three explicit asymptotic constructions that improve upon the previously best known lower bound C > 6.278944 by O'Donnell and Tan, obtained via recursive composition. The first uses their construction with the lexicographic function 𝓁⟨2/3⟩ of measure 2/3 to demonstrate that C >= 4+3 log_4 (3) > 6.377444. The second generalizes their construction to biased functions and obtains C > 6.413846 using 𝓁⟨Φ⟩, where Φ is the inverse golden ratio. The third, independent, construction gives C > 6.454784, even for monotone functions.
Beyond modest improvements to the value of C, our constructions shed some new light on the properties sought in potential counterexamples to the conjecture.
本文转载自久章智能微信公众号（原文发布于 2020-10-19），内容保持原貌。扫码关注公众号「久章智能」，第一时间获取系列文章。阅读原文 ↗