{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,8]],"date-time":"2025-03-08T05:25:15Z","timestamp":1741411515344,"version":"3.38.0"},"reference-count":20,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2024,12,20]],"date-time":"2024-12-20T00:00:00Z","timestamp":1734652800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2024,12,20]],"date-time":"2024-12-20T00:00:00Z","timestamp":1734652800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"name":"EPFL Lausanne"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Combinatorica"],"published-print":{"date-parts":[[2025,2]]},"abstract":"Abstract<\/jats:title>\n In this paper, we prove that the Fourier entropy of an n<\/jats:italic>-dimensional boolean function f<\/jats:italic> can be upper-bounded by \n \n $$O(I(f)+ \\sum \\limits _{k\\in [n]}I_k(f)\\log \\frac{1}{I_k(f)})$$<\/jats:tex-math>\n \n \n O<\/mml:mi>\n (<\/mml:mo>\n I<\/mml:mi>\n \n (<\/mml:mo>\n f<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n +<\/mml:mo>\n \n \u2211<\/mml:mo>\n \n k<\/mml:mi>\n \u2208<\/mml:mo>\n [<\/mml:mo>\n n<\/mml:mi>\n ]<\/mml:mo>\n <\/mml:mrow>\n <\/mml:munder>\n \n I<\/mml:mi>\n k<\/mml:mi>\n <\/mml:msub>\n \n (<\/mml:mo>\n f<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n log<\/mml:mo>\n \n 1<\/mml:mn>\n \n \n I<\/mml:mi>\n k<\/mml:mi>\n <\/mml:msub>\n \n (<\/mml:mo>\n f<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:mrow>\n <\/mml:mfrac>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>, where I<\/jats:italic>(f<\/jats:italic>) is its total influence and \n \n $$I_k(f)$$<\/jats:tex-math>\n \n \n \n I<\/mml:mi>\n k<\/mml:mi>\n <\/mml:msub>\n \n (<\/mml:mo>\n f<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula> is the influence of the k<\/jats:italic>-th coordinate. There is no strict quantitative relationship between our bound with the known bounds for the Fourier-Min-Entropy-Influence conjecture \n \n $$O(I(f)\\log I(f))$$<\/jats:tex-math>\n \n \n O<\/mml:mi>\n (<\/mml:mo>\n I<\/mml:mi>\n (<\/mml:mo>\n f<\/mml:mi>\n )<\/mml:mo>\n log<\/mml:mo>\n I<\/mml:mi>\n (<\/mml:mo>\n f<\/mml:mi>\n )<\/mml:mo>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula> and \n \n $$O(I(f)^2)$$<\/jats:tex-math>\n \n \n O<\/mml:mi>\n (<\/mml:mo>\n I<\/mml:mi>\n \n \n (<\/mml:mo>\n f<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n 2<\/mml:mn>\n <\/mml:msup>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>. The proof is elementary and uses iterative bounds on moments of Fourier coefficients over different levels to estimate the Fourier entropy as its derivative.<\/jats:p>","DOI":"10.1007\/s00493-024-00133-z","type":"journal-article","created":{"date-parts":[[2025,1,10]],"date-time":"2025-01-10T11:05:13Z","timestamp":1736507113000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["A New Bound for the Fourier-Entropy-Influence Conjecture"],"prefix":"10.1007","volume":"45","author":[{"given":"Xiao","family":"Han","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2024,12,20]]},"reference":[{"doi-asserted-by":"crossref","unstructured":"Mossel, E., O\u2019Donnell, R., Oleszkiewicz, K.: Noise stability of functions with low influences: invariance and optimality. In: 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS\u201905), pp. 295\u2013341 (2010)","key":"133_CR1","DOI":"10.4007\/annals.2010.171.295"},{"doi-asserted-by":"crossref","unstructured":"Kahn, J., Kalai, G., Linial, N.: The influence of variables on Boolean functions, pp. 68\u201380. Institute for Mathematical Studies in the Social Sciences (1989)","key":"133_CR2","DOI":"10.1109\/SFCS.1988.21923"},{"issue":"1","key":"133_CR3","doi-asserted-by":"publisher","first-page":"27","DOI":"10.1007\/PL00009809","volume":"18","author":"E Friedgut","year":"1998","unstructured":"Friedgut, E.: Boolean functions with low average sensitivity depend on few coordinates. Combinatorica 18(1), 27\u201335 (1998)","journal-title":"Combinatorica"},{"issue":"10","key":"133_CR4","doi-asserted-by":"publisher","first-page":"2993","DOI":"10.1090\/S0002-9939-96-03732-X","volume":"124","author":"E Friedgut","year":"1996","unstructured":"Friedgut, E., Kalai, G.: Every monotone graph property has a sharp threshold. Proc. Am. Math. Soc. 124(10), 2993\u20133002 (1996)","journal-title":"Proc. Am. Math. Soc."},{"issue":"3","key":"133_CR5","doi-asserted-by":"publisher","first-page":"438","DOI":"10.1007\/s000390050015","volume":"7","author":"J Bourgain","year":"1997","unstructured":"Bourgain, J., Kalai, G.: Influences of variables and threshold intervals under group symmetries. Geom. Funct. Anal. 7(3), 438\u2013461 (1997)","journal-title":"Geom. Funct. Anal."},{"issue":"3","key":"133_CR6","doi-asserted-by":"publisher","first-page":"543","DOI":"10.1006\/jcss.1995.1043","volume":"50","author":"Y Mansour","year":"1995","unstructured":"Mansour, Y.: An $$O(n^{ \\log \\log n})$$ learning algorithm for DNF under the uniform distribution. J. Comput. Syst. Sci. 50(3), 543\u2013550 (1995)","journal-title":"J. Comput. Syst. Sci."},{"doi-asserted-by":"crossref","unstructured":"Gopalan, P., Kalai, A.T., Klivans, A.R.: Agnostically learning decision trees. In: Proceedings of the Fortieth Annual ACM Symposium on Theory of Computing, pp. 527\u2013536 (2008)","key":"133_CR7","DOI":"10.1145\/1374376.1374451"},{"key":"133_CR8","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9781139924160","volume-title":"Noise Sensitivity of Boolean Functions and Percolation","author":"C Garban","year":"2014","unstructured":"Garban, C., Steif, J.E.: Noise Sensitivity of Boolean Functions and Percolation. Cambridge University Press, Cambridge (2014)"},{"issue":"1","key":"133_CR9","doi-asserted-by":"publisher","first-page":"19","DOI":"10.1007\/s11511-010-0051-x","volume":"205","author":"C Garban","year":"2010","unstructured":"Garban, C., Pete, G., Schramm, O.: The Fourier spectrum of critical percolation. Acta Math. 205(1), 19\u2013104 (2010)","journal-title":"Acta Math."},{"issue":"12","key":"133_CR10","doi-asserted-by":"publisher","first-page":"122206","DOI":"10.1063\/1.4769269","volume":"53","author":"A Montanaro","year":"2012","unstructured":"Montanaro, A.: Some applications of hypercontractive inequalities in quantum information theory. J. Math. Phys. 53(12), 122206 (2012)","journal-title":"J. Math. Phys."},{"issue":"4","key":"133_CR11","doi-asserted-by":"publisher","first-page":"1097","DOI":"10.1007\/s00039-020-00544-2","volume":"30","author":"E Kelman","year":"2020","unstructured":"Kelman, E., Kindler, G., Lifshitz, N., Minzer, D., Safra, M.: Towards a proof of the Fourier-Entropy conjecture? Geom. Funct. Anal. 30(4), 1097\u20131138 (2020)","journal-title":"Geom. Funct. Anal."},{"key":"133_CR12","doi-asserted-by":"publisher","first-page":"92","DOI":"10.1016\/j.tcs.2016.05.006","volume":"654","author":"S Chakraborty","year":"2016","unstructured":"Chakraborty, S., Kulkarni, R., Lokam, S.V., Saurabh, N.: Upper bounds on Fourier entropy. Theor. Comput. Sci. 654, 92\u2013112 (2016)","journal-title":"Theor. Comput. Sci."},{"doi-asserted-by":"crossref","unstructured":"O\u2019Donnell, R., Tan, L.Y.: A composition theorem for the Fourier entropy-influence conjecture. In: International Colloquium on Automata, Languages, and Programming, pp. 780\u2013791. Springer, Berlin (2013)","key":"133_CR13","DOI":"10.1007\/978-3-642-39206-1_66"},{"doi-asserted-by":"crossref","unstructured":"O\u2019Donnell, R., Wright, J., Zhou, Y.: The Fourier entropy-influence conjecture for certain classes of Boolean functions. In: International Colloquium on Automata, Languages, and Programming, pp. 330\u2013341. Springer, Berlin (2011)","key":"133_CR14","DOI":"10.1007\/978-3-642-22006-7_28"},{"unstructured":"Shalev, G:. On the Fourier entropy influence conjecture for extremal classes (2018). arXiv:1806.03646","key":"133_CR15"},{"issue":"4","key":"133_CR16","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/3470860","volume":"13","author":"S Arunachalam","year":"2021","unstructured":"Arunachalam, S., Chakraborty, S., Kouck\u00fd, M., Saurabh, N., De Wolf, R.: Improved bounds on Fourier entropy and min-entropy. ACM Trans. Comput. Theory 13(4), 1\u201340 (2021)","journal-title":"ACM Trans. Comput. Theory"},{"doi-asserted-by":"crossref","unstructured":"Wan, A., Wright, J., Wu, C.: Decision trees, protocols and the entropy-influence conjecture. In: Proceedings of the 5th Conference on Innovations in Theoretical Computer Science, pp. 67\u201380 (2014)","key":"133_CR17","DOI":"10.1145\/2554797.2554806"},{"key":"133_CR18","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9781139814782","volume-title":"Analysis of Boolean Functions","author":"R O\u2019Donnell","year":"2014","unstructured":"O\u2019Donnell, R.: Analysis of Boolean Functions. Cambridge University Press, Cambridge (2014)"},{"issue":"1","key":"133_CR19","doi-asserted-by":"publisher","first-page":"269","DOI":"10.1007\/BF02785861","volume":"131","author":"J Bourgain","year":"2002","unstructured":"Bourgain, J.: On the distribution of the Fourier spectrum of Boolean functions. Isr. J. Math. 131(1), 269\u2013276 (2002)","journal-title":"Isr. J. Math."},{"unstructured":"Kalai, G.: The entropy\/influence conjecture (2007). https:\/\/terrytao.wordpress.com\/2007\/08\/16\/gil-kalai-the-entropyinfluence-conjecture\/. Accessed 26 Oct 2019","key":"133_CR20"}],"container-title":["Combinatorica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00493-024-00133-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00493-024-00133-z\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00493-024-00133-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,3,7]],"date-time":"2025-03-07T13:39:45Z","timestamp":1741354785000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00493-024-00133-z"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,12,20]]},"references-count":20,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2025,2]]}},"alternative-id":["133"],"URL":"https:\/\/doi.org\/10.1007\/s00493-024-00133-z","relation":{},"ISSN":["0209-9683","1439-6912"],"issn-type":[{"type":"print","value":"0209-9683"},{"type":"electronic","value":"1439-6912"}],"subject":[],"published":{"date-parts":[[2024,12,20]]},"assertion":[{"value":"1 March 2024","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"21 November 2024","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"28 November 2024","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"20 December 2024","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}],"article-number":"4"}}