Project 1: The Entropy-Influence Conjecture
The entropy-influence conjecture was originally asked by Ehud Friedgut and Gil Kalai in 1996.
For a boolean function , its influence is .
The entropy of is defined by . The entropy-influence conjecture asks, could we prove that for any boolean function .
In my knowledge, the best known (general) result was given by Gopalan, Servedio, Tal and Wigderson [1]. They proved that where is the sensitivity of . By plugging-in a robust version of [1], a result of Lovett, Tal and Zhang [2] shows that we can replace by the robust sensitivity. In particular, it shows for any width- DNF .
The entropy-influence conjecture is known true for some classes of boolean functions. However it is still hard for general boolean functions. It is even non-trivial to prove that .
An easier question is the min-entropy influence conjecture. Which asks could we prove that . By Friedgut’s juntas theorem, we are able to prove . It is interesting to ask could we prove this true for entropy, i.e., could we prove that ?
For certain classes:
- KKL theorem implies min-entropy influence conjecture holds for monotone functions.
- O’Donnell, Wright and Zhou [3] proved entropy influence conjecture holds for symmetric functions.
[1] Gopalan, P., Servedio, R., Tal, A. and Wigderson, A., 2016. Degree and sensitivity: tails of two distributions. arXiv preprint arXiv:1604.07432.
[2] Lovett, S., Tal, A. and Zhang, J., 2018. The robust sensitivity of boolean functions. In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms (pp. 1822-1833). Society for Industrial and Applied Mathematics.
[3] O’Donnell, R., Wright, J. and Zhou, Y. 2011. The Fourier Entropy-Influence Conjecture for certain classes of Boolean functions. In Proceedings of ICALP 2011.
Rupei Xu 4:04 pm on November 1, 2019 Permalink | Log in to Reply
Thank you for sharing your treasure, Jiapeng! That’s indeed a very interesting problem! Could you please provide a link of your result you mentioned?
LikeLike
Jiapeng Zhang 5:59 pm on November 1, 2019 Permalink | Log in to Reply
Which result? ? I don’t think there is a link. It is a folklore.
LikeLike
Rupei Xu 6:02 pm on November 1, 2019 Permalink
“By Friedgut’s juntas theorem, we are able to prove…”
LikeLike
Jiapeng Zhang 6:04 pm on November 1, 2019 Permalink | Log in to Reply
Yes, there is no link for this result. It is an unpublished observation. It could be a good exercise.
LikeLiked by 1 person
Rupei Xu 6:08 pm on November 1, 2019 Permalink | Log in to Reply
Ok, thank you.
LikeLike
Gil Kalai 4:08 pm on November 4, 2019 Permalink | Log in to Reply
This is indeed a very nice problem and thankful to Jiapeng Zhang for proposing it. Two quick remarks are that I wrote in 2007 a post about it on Terry Tao’s blog https://terrytao.wordpress.com/2007/08/16/gil-kalai-the-entropyinfluence-conjecture/ , the second remark is that I heard about some recent soon-to-be-published works related to the conjecture (but not solving it).
LikeLiked by 1 person
Jiapeng Zhang 4:16 pm on November 4, 2019 Permalink | Log in to Reply
Thank you Gil. I will add more references about works in this conjecture soon. There are a lot of nice results (after your blog 😉 )
LikeLike
Jiapeng Zhang 4:50 pm on December 1, 2019 Permalink | Log in to Reply
Dear Gil, do you mean this paper? https://arxiv.org/pdf/1911.10579.pdf
LikeLiked by 1 person
Gil Kalai 6:32 pm on December 1, 2019 Permalink
Dear Jiapeng, yes this is what I meant!
LikeLike
Rupei Xu 7:37 pm on December 6, 2020 Permalink
Recently this paper was presented in FOCS 2020, here is the link to the talk: https://www.youtube.com/watch?v=X3mkTUmlX2Y
LikeLike
A new PolyTCS blog! | Combinatorics and more 2:05 pm on March 6, 2020 Permalink | Log in to Reply
[…] At this stage the blog raised possible projects to pursue. A few days ago Rupei Xu discussed a second possible exciting project: Project 2: Is Semi-Definite Programming (SDP) Polynomial-Time Solvable? The first project-proposal (Nov 1, 2019 by Jiapeng Zhang) was Project 1: The Entropy-Influence Conjecture. […]
LikeLike