Fourier entropy influence conjecture for random linear threshold functions

DOI10.1007/978-3-319-77404-6_21zbMATH Open1487.94208arXiv1903.11635OpenAlexW2791818749MaRDI QIDQ2294693FDOQ2294693

Authors: Sourav Chakraborty, Sushrut Karmalkar, Srijita Kundu, Satyanarayana V. Lokam, Nitin Saurabh 

Publication date: 12 February 2020

Abstract: The Fourier-Entropy Influence (FEI) Conjecture states that for any Boolean function $f:{+1,-1}^{n}o+1,-1$, the Fourier entropy of $f$ is at most its influence up to a universal constant factor. While the FEI conjecture has been proved for many classes of Boolean functions, it is still not known whether it holds for the class of Linear Threshold Functions. A natural question is: Does the FEI conjecture hold for a `random' linear threshold function? In this paper, we answer this question in the affirmative. We consider two natural distributions on the weights defining a linear threshold function, namely uniform distribution on $[-1,1]$ and Normal distribution.

Full work available at URL: https://arxiv.org/abs/1903.11635

Recommendations

• A composition theorem for the Fourier entropy-influence conjecture
• Improved bounds on Fourier entropy and min-entropy
• The Fourier entropy-influence conjecture for certain classes of Boolean functions
• Upper bounds on Fourier entropy
• Upper bounds on Fourier entropy

Mathematics Subject Classification ID

Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87) Boolean functions (94D10)

Cited In (8)

• Proving the conjecture of O'Donnell in certain cases and disproving its general validity
• Separation results for Boolean function classes
• Upper bounds on Fourier entropy
• Decision trees, protocols and the entropy-influence conjecture
• Improved bounds on Fourier entropy and min-entropy
• A note on the entropy/influence conjecture
• Upper bounds on Fourier entropy
• The Fourier entropy-influence conjecture for certain classes of Boolean functions

This page was built for publication: Fourier entropy influence conjecture for random linear threshold functions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2294693)