## 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 ?

[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.

## Rupei Xu 4:04 pm

onNovember 1, 2019 Permalink | Log in to ReplyThank 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

onNovember 1, 2019 Permalink | Log in to ReplyWhich result? ? I don’t think there is a link. It is a folklore.

LikeLike

## Rupei Xu 6:02 pm

onNovember 1, 2019 Permalink“By Friedgut’s juntas theorem, we are able to prove…”

LikeLike

## Jiapeng Zhang 6:04 pm

onNovember 1, 2019 Permalink | Log in to ReplyYes, there is no link for this result. It is an unpublished observation. It could be a good exercise.

LikeLike

## Rupei Xu 6:08 pm

onNovember 1, 2019 Permalink | Log in to ReplyOk, thank you.

LikeLike

## Gil Kalai 4:08 pm

onNovember 4, 2019 Permalink | Log in to ReplyThis 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).

LikeLike

## Jiapeng Zhang 4:16 pm

onNovember 4, 2019 Permalink | Log in to ReplyThank 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

onDecember 1, 2019 Permalink | Log in to ReplyDear Gil, do you mean this paper? https://arxiv.org/pdf/1911.10579.pdf

LikeLike

## Gil Kalai 6:32 pm

onDecember 1, 2019 PermalinkDear Jiapeng, yes this is what I meant!

LikeLike

## A new PolyTCS blog! | Combinatorics and more 2:05 pm

onMarch 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