{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,11,19]],"date-time":"2023-11-19T09:26:50Z","timestamp":1700386010983},"reference-count":71,"publisher":"Association for Computing Machinery (ACM)","issue":"4","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Comput. Theory"],"published-print":{"date-parts":[[2021,12,31]]},"abstract":"\n Given a Boolean function f:{ -1,1} ^{n}\u2192 { -1,1, define the\n Fourier distribution<\/jats:italic>\n to be the distribution on subsets of [n], where each S \u2286 [n] is sampled with probability f \u02c6 (S)\n 2<\/jats:sup>\n . The Fourier Entropy-influence (FEI) conjecture of Friedgut and Kalai\u00a0[28] seeks to relate two fundamental measures associated with the Fourier distribution: does there exist a universal constant C > 0 such that H(f\n \u02c62<\/jats:sup>\n ) \u2264 C \u22c5 Inf (f), where H\n (f\u02c62)<\/jats:sup>\n is the Shannon entropy of the Fourier distribution of\n f<\/jats:italic>\n and Inf(f) is the total influence of\n f<\/jats:italic>\n <\/jats:p>\n \n In this article, we present three new contributions toward the FEI conjecture:\n \n \n (1)<\/jats:label>\n \n Our first contribution shows that H(f\n \u02c62<\/jats:sup>\n ) \u2264 2 \u22c5 aUC\n \u2295<\/jats:sup>\n (f), where aUC\n \u2295<\/jats:sup>\n (f) is the average unambiguous parity-certificate complexity of\n f<\/jats:italic>\n . This improves upon several bounds shown by Chakraborty et\u00a0al.\u00a0[20]. We further improve this bound for unambiguous DNFs. We also discuss how our work makes Mansour's conjecture for DNFs a natural next step toward resolution of the FEI conjecture.\n <\/jats:p>\n <\/jats:list-item>\n \n (2)<\/jats:label>\n \n We next consider the weaker\n Fourier Min-entropy-influence<\/jats:italic>\n (FMEI) conjecture posed by O'Donnell and others\u00a0[50, 53], which asks if H \u221e\n f\u02c62)<\/jats:sup>\n \u2264 C \u22c5 Inf(f), where H \u221e\n f\u02c62)<\/jats:sup>\n is the min-entropy of the Fourier distribution. We show H\n \u221e<\/jats:sub>\n (f\u02c62)<\/jats:sup>\n \u2264 2\u22c5C\n min<\/jats:sub>\n \u2295<\/jats:sup>\n (f), where C\n min<\/jats:sub>\n \u2295<\/jats:sup>\n (f) is the minimum parity-certificate complexity of\n f<\/jats:italic>\n . We also show that for all \u03b5\u22650, we have H\n \u221e<\/jats:sub>\n (f\u02c62)<\/jats:sup>\n \u22642 log\u2061(\u2225f\n \u02c6<\/jats:sup>\n \u22251,\u03b5\/(1\u2212\u03b5)), where \u2225f\n \u02c6<\/jats:sup>\n \u22251,\u03b5 is the approximate spectral norm of\n f<\/jats:italic>\n . As a corollary, we verify the FMEI conjecture for the class of read-\n k<\/jats:italic>\n DNFs (for constant\u00a0\n k<\/jats:italic>\n ).\n <\/jats:p>\n <\/jats:list-item>\n \n (3)<\/jats:label>\n \n Our third contribution is to better understand implications of the FEI conjecture for the structure of polynomials that 1\/3-approximate a Boolean function on the Boolean cube. We pose a conjecture: no\n flat polynomial<\/jats:italic>\n (whose non-zero Fourier coefficients have the same magnitude) of degree\n d<\/jats:italic>\n and sparsity 2\n \u03c9(d)<\/jats:sup>\n can 1\/3-approximate a Boolean function. This conjecture is known to be true assuming FEI, and we prove the conjecture unconditionally (i.e., without assuming the FEI conjecture) for a class of polynomials. We discuss an intriguing connection between our conjecture and the constant for the Bohnenblust-Hille inequality, which has been extensively studied in functional analysis.\n <\/jats:p>\n <\/jats:list-item>\n <\/jats:list>\n <\/jats:p>","DOI":"10.1145\/3470860","type":"journal-article","created":{"date-parts":[[2021,9,1]],"date-time":"2021-09-01T19:28:46Z","timestamp":1630524526000},"page":"1-40","update-policy":"http:\/\/dx.doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":2,"title":["Improved Bounds on Fourier Entropy and Min-entropy"],"prefix":"10.1145","volume":"13","author":[{"given":"Srinivasan","family":"Arunachalam","sequence":"first","affiliation":[{"name":"IBM Research, New York, USA"}]},{"given":"Sourav","family":"Chakraborty","sequence":"additional","affiliation":[{"name":"Indian Statistical Institute, Kolkata, India"}]},{"given":"Michal","family":"Kouck\u00fd","sequence":"additional","affiliation":[{"name":"Computer Science Institute of Charles University, Prague, Czech Republic"}]},{"given":"Nitin","family":"Saurabh","sequence":"additional","affiliation":[{"name":"Technion-IIT, Haifa, Israel"}]},{"given":"Ronald","family":"de Wolf","sequence":"additional","affiliation":[{"name":"QuSoft, CWI and University of Amsterdam, Amsterdam, the Netherlands"}]}],"member":"320","published-online":{"date-parts":[[2021,9]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1137\/15M1050902"},{"key":"e_1_2_1_2_1","volume-title":"Proceedings of the 5th Conference on Innovations in Theoretical Computer Science (ITCS'14)","author":"Akavia A.","unstructured":"A. Akavia , A. Bogdanov , S. Guo , A. Kamath , and A. Rosen . 2014. Candidate weak pseudorandom functions in ACMOD2 . In Proceedings of the 5th Conference on Innovations in Theoretical Computer Science (ITCS'14) . ACM, 251\u2013260. A. Akavia, A. Bogdanov, S. Guo, A. Kamath, and A. Rosen. 2014. Candidate weak pseudorandom functions in ACMOD2. In Proceedings of the 5th Conference on Innovations in Theoretical Computer Science (ITCS'14). ACM, 251\u2013260."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jfa.2013.08.013"},{"key":"e_1_2_1_4_1","doi-asserted-by":"crossref","unstructured":"N. Alon and J. Spencer. 2000. The Probabilistic Method. Wiley-Interscience Series in Discrete Mathematics and Optimization. N. Alon and J. Spencer. 2000. The Probabilistic Method. Wiley-Interscience Series in Discrete Mathematics and Optimization.","DOI":"10.1002\/0471722154"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2011.v007a004"},{"key":"e_1_2_1_6_1","volume-title":"Proceedings of the 31st Conference on Computational Complexity (CCC'16)","author":"Ambainis A.","unstructured":"A. Ambainis , M. Kokainis , and R. Kothari . 2016. Nearly optimal separations between communication (or query) complexity and partitions . In Proceedings of the 31st Conference on Computational Complexity (CCC'16) . 4:1\u20134:14. A. Ambainis, M. Kokainis, and R. Kothari. 2016. Nearly optimal separations between communication (or query) complexity and partitions. In Proceedings of the 31st Conference on Computational Complexity (CCC'16). 4:1\u20134:14."},{"key":"e_1_2_1_7_1","volume-title":"Proceedings of the 37th International Symposium on Theoretical Aspects of Computer Science (STACS'20)","volume":"19","author":"Arunachalam S.","year":"2020","unstructured":"S. Arunachalam , S. Chakraborty , M. Kouck\u00fd , N. Saurabh , and R. de Wolf . 2020 . Improved bounds on fourier entropy and min-entropy . In Proceedings of the 37th International Symposium on Theoretical Aspects of Computer Science (STACS'20) (LIPIcs, Vol. 154). 45:1\u201345: 19 . S. Arunachalam, S. Chakraborty, M. Kouck\u00fd, N. Saurabh, and R. de Wolf. 2020. Improved bounds on fourier entropy and min-entropy. In Proceedings of the 37th International Symposium on Theoretical Aspects of Computer Science (STACS'20)(LIPIcs, Vol. 154). 45:1\u201345:19."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.aim.2014.07.029"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/502090.502097"},{"key":"e_1_2_1_10_1","volume-title":"Proceedings of the 8th Innovations in Theoretical Computer Science Conference (ITCS'17)","author":"Ben-David S.","unstructured":"S. Ben-David , P. Hatami , and A. Tal . 2017. Low-sensitivity functions from unambiguous certificates . In Proceedings of the 8th Innovations in Theoretical Computer Science Conference (ITCS'17) . 28:1\u201328:23. S. Ben-David, P. Hatami, and A. Tal. 2017. Low-sensitivity functions from unambiguous certificates. In Proceedings of the 8th Innovations in Theoretical Computer Science Conference (ITCS'17). 28:1\u201328:23."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.2307\/1968255"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(97)00131-2"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/s000390050015"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1109\/12.45216"},{"key":"e_1_2_1_15_1","first-page":"3","article-title":"Multipartite entanglement in XOR games","volume":"13","author":"Bri\u00ebt J.","year":"2013","unstructured":"J. Bri\u00ebt , H. Buhrman , T. Lee , and T. Vidick . 2013 . Multipartite entanglement in XOR games . Quant. Info. Comput. 13 , 3 - 4 (2013), 334\u2013360. Retrieved from https:\/\/arXiv:0911.4007. J. Bri\u00ebt, H. Buhrman, T. Lee, and T. Vidick. 2013. Multipartite entanglement in XOR games. Quant. Info. Comput. 13, 3-4 (2013), 334\u2013360. Retrieved from https:\/\/arXiv:0911.4007.","journal-title":"Quant. Info. Comput."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(01)00144-X"},{"key":"e_1_2_1_17_1","volume-title":"Proceedings of the 40th International Colloquium on Automata, Languages, and Programming (ICALP'13)","author":"Bun M.","unstructured":"M. Bun and J. Thaler . 2013. Dual lower bounds for approximate degree and markov-bernstein inequalities . In Proceedings of the 40th International Colloquium on Automata, Languages, and Programming (ICALP'13) . 303\u2013314. M. Bun and J. Thaler. 2013. Dual lower bounds for approximate degree and markov-bernstein inequalities. In Proceedings of the 40th International Colloquium on Automata, Languages, and Programming (ICALP'13). 303\u2013314."},{"key":"e_1_2_1_18_1","volume-title":"Proceedings of the 35th Computational Complexity Conference (CCC'20)","volume":"15","author":"Chakraborty S.","unstructured":"S. Chakraborty , A. Chattopadhyay , N. S. Mande , and M. Paraashar . 2020. Quantum query-to-communication simulation needs a logarithmic overhead . In Proceedings of the 35th Computational Complexity Conference (CCC'20) (LIPIcs, Vol. 169). 32:1\u201332: 15 . S. Chakraborty, A. Chattopadhyay, N. S. Mande, and M. Paraashar. 2020. Quantum query-to-communication simulation needs a logarithmic overhead. In Proceedings of the 35th Computational Complexity Conference (CCC'20)(LIPIcs, Vol. 169). 32:1\u201332:15."},{"key":"e_1_2_1_19_1","volume-title":"Proceedings of the 13th Latin American Theoretical Informatics Symposium (LATIN'18)","author":"Chakraborty S.","unstructured":"S. Chakraborty , S. Karmalkar , S. Kundu , S. V. Lokam , and N. Saurabh . 2018. Fourier entropy-influence conjecture for random linear threshold functions . In Proceedings of the 13th Latin American Theoretical Informatics Symposium (LATIN'18) . 275\u2013289. S. Chakraborty, S. Karmalkar, S. Kundu, S. V. Lokam, and N. Saurabh. 2018. Fourier entropy-influence conjecture for random linear threshold functions. In Proceedings of the 13th Latin American Theoretical Informatics Symposium (LATIN'18). 275\u2013289."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2016.05.006"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2018.04.006"},{"key":"e_1_2_1_22_1","volume-title":"Proceedings of the 7th Conference on Innovations in Theoretical Computer Science (ITCS'16)","author":"Cohen G.","unstructured":"G. Cohen and I. Shinkar . 2016. The complexity of DNF of parities . In Proceedings of the 7th Conference on Innovations in Theoretical Computer Science (ITCS'16) . ACM, 47\u201358. G. Cohen and I. Shinkar. 2016. The complexity of DNF of parities. In Proceedings of the 7th Conference on Innovations in Theoretical Computer Science (ITCS'16). ACM, 47\u201358."},{"key":"e_1_2_1_23_1","doi-asserted-by":"crossref","unstructured":"T. M. Cover and J. A. Thomas. 1991. Elements of Information Theory. John Wiley & Sons. T. M. Cover and J. A. Thomas. 1991. Elements of Information Theory. John Wiley & Sons.","DOI":"10.1002\/0471200611"},{"key":"e_1_2_1_24_1","unstructured":"B. Das M. Pal and V. Visavaliya. 2011. The Entropy Influence Conjecture Revisited. Retrieved from https:\/\/arxiv:1110.4301. B. Das M. Pal and V. Visavaliya. 2011. The Entropy Influence Conjecture Revisited. Retrieved from https:\/\/arxiv:1110.4301."},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.4007\/annals.2011.174.1.13"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jfa.2010.01.008"},{"key":"e_1_2_1_27_1","volume-title":"Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing (STOC'20)","author":"Eldan R.","unstructured":"R. Eldan and R. Gross . 2020. Concentration on the Boolean hypercube via pathwise stochastic analysis . In Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing (STOC'20) . 208\u2013221. R. Eldan and R. Gross. 2020. Concentration on the Boolean hypercube via pathwise stochastic analysis. In Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing (STOC'20). 208\u2013221."},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9939-96-03732-X"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2015.69"},{"key":"e_1_2_1_30_1","volume-title":"Proceedings of the 21st Annual Conference on Learning Theory (COLT'08)","author":"Gopalan P.","unstructured":"P. Gopalan , A. Kalai , and A. R. Klivans . 2008. A query algorithm for agnostically learning DNF? In Proceedings of the 21st Annual Conference on Learning Theory (COLT'08) . 515\u2013516. P. Gopalan, A. Kalai, and A. R. Klivans. 2008. A query algorithm for agnostically learning DNF? In Proceedings of the 21st Annual Conference on Learning Theory (COLT'08). 515\u2013516."},{"key":"e_1_2_1_31_1","volume-title":"Proceedings of the 40th Annual ACM Symposium on Theory of Computing (STOC'08)","author":"Gopalan P.","unstructured":"P. Gopalan , A. T. Kalai , and A. Klivans . 2008. Agnostically learning decision trees . In Proceedings of the 40th Annual ACM Symposium on Theory of Computing (STOC'08) . 527\u2013536. P. Gopalan, A. T. Kalai, and A. Klivans. 2008. Agnostically learning decision trees. In Proceedings of the 40th Annual ACM Symposium on Theory of Computing (STOC'08). 527\u2013536."},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-013-0068-6"},{"key":"e_1_2_1_33_1","volume-title":"Proceedings of the 31st Conference on Computational Complexity (CCC'16)","author":"Gopalan P.","unstructured":"P. Gopalan , R. A. Servedio , A. Tal , and A. Wigderson . 2016. Degree and sensitivity: Tails of two distributions . In Proceedings of the 31st Conference on Computational Complexity (CCC'16) . 13:1\u201313:23. P. Gopalan, R. A. Servedio, A. Tal, and A. Wigderson. 2016. Degree and sensitivity: Tails of two distributions. In Proceedings of the 31st Conference on Computational Complexity (CCC'16). 13:1\u201313:23."},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.2307\/2373688"},{"key":"e_1_2_1_35_1","unstructured":"R. Hod. 2017. Improved Lower Bounds for the Fourier Entropy\/Influence Conjecture via Lexicographic Functions. Retrieved from https:\/\/arxiv:1711.00762. R. Hod. 2017. Improved Lower Bounds for the Fourier Entropy\/Influence Conjecture via Lexicographic Functions. Retrieved from https:\/\/arxiv:1711.00762."},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1988.21923"},{"key":"e_1_2_1_37_1","unstructured":"G. Kalai. 2007. The Entropy\/Influence Conjecture. Retrieved from https:\/\/terrytao.wordpress.com\/2007\/08\/16\/gil-kalai-the-entropyinfluence-conjecture\/. G. Kalai. 2007. The Entropy\/Influence Conjecture. Retrieved from https:\/\/terrytao.wordpress.com\/2007\/08\/16\/gil-kalai-the-entropyinfluence-conjecture\/."},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.disc.2012.07.031"},{"key":"e_1_2_1_39_1","volume-title":"Proceedings of the 61st IEEE Annual Symposium on Foundations of Computer Science (FOCS'20)","author":"Kelman E.","unstructured":"E. Kelman , G. Kindler , N. Lifshitz , D. Minzer , and M. Safra . 2020. Towards a proof of the fourier-entropy conjecture? . In Proceedings of the 61st IEEE Annual Symposium on Foundations of Computer Science (FOCS'20) . IEEE, 247\u2013258. E. Kelman, G. Kindler, N. Lifshitz, D. Minzer, and M. Safra. 2020. Towards a proof of the fourier-entropy conjecture?. In Proceedings of the 61st IEEE Annual Symposium on Foundations of Computer Science (FOCS'20). IEEE, 247\u2013258."},{"key":"e_1_2_1_40_1","volume-title":"Proceedings of the 23rd Conference on Learning Theory (COLT'10)","author":"Klivans A.","unstructured":"A. Klivans , H. Lee , and A. Wan . 2010. Mansour's conjecture is true for random DNF formulas . In Proceedings of the 23rd Conference on Learning Theory (COLT'10) . 368\u2013380. A. Klivans, H. Lee, and A. Wan. 2010. Mansour's conjecture is true for random DNF formulas. In Proceedings of the 23rd Conference on Learning Theory (COLT'10). 368\u2013380."},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1561\/0400000040"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/174130.174138"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1093\/qmath\/os-1.1.164"},{"key":"e_1_2_1_44_1","volume-title":"Proccedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing (STOC'20)","author":"Lovett S.","unstructured":"S. Lovett , K. Wu , and J. Zhang . 2020. Decision list compression by mild random restrictions . In Proccedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing (STOC'20) . ACM, 247\u2013254. S. Lovett, K. Wu, and J. Zhang. 2020. Decision list compression by mild random restrictions. In Proccedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing (STOC'20). ACM, 247\u2013254."},{"key":"e_1_2_1_45_1","volume-title":"Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing (STOC'19)","author":"Lovett S.","unstructured":"S. Lovett and J. Zhang . 2019. DNF sparsification beyond sunflowers . In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing (STOC'19) . ACM, 454\u2013460. S. Lovett and J. Zhang. 2019. DNF sparsification beyond sunflowers. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing (STOC'19). ACM, 454\u2013460."},{"key":"e_1_2_1_46_1","volume-title":"Theoretical Advances in Neural Computation and Learning, V. Roychowdhury, K.-Y","author":"Mansour Y.","unstructured":"Y. Mansour . 1994. Learning Boolean functions via the fourier transform . In Theoretical Advances in Neural Computation and Learning, V. Roychowdhury, K.-Y . Siu, and A. Orlitsky (Eds.). Springer U.S. , 391\u2013424. Y. Mansour. 1994. Learning Boolean functions via the fourier transform. In Theoretical Advances in Neural Computation and Learning, V. Roychowdhury, K.-Y. Siu, and A. Orlitsky (Eds.). Springer U.S., 391\u2013424."},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1995.1043"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1063\/1.4769269"},{"key":"e_1_2_1_49_1","unstructured":"A. Montanaro and T. Osborne. 2009. On the communication complexity of XOR functions. Retrieved from https:\/\/arXiv:0909.3392. A. Montanaro and T. Osborne. 2009. On the communication complexity of XOR functions. Retrieved from https:\/\/arXiv:0909.3392."},{"key":"e_1_2_1_50_1","volume-title":"Analysis of Boolean Functions","author":"O'Donnell R.","unstructured":"R. O'Donnell . 2014. Analysis of Boolean Functions . Cambridge University Press . R. O'Donnell. 2014. Analysis of Boolean Functions. Cambridge University Press."},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-39206-1_66"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2014.22"},{"key":"e_1_2_1_53_1","volume-title":"Proceedings of the 38th International Colloquium on Automata, Languages and Programming (ICALP'11)","author":"O'Donnell R.","unstructured":"R. O'Donnell , J. Wright , and Y. Zhou . 2011. The fourier entropy-influence conjecture for certain classes of Boolean functions . In Proceedings of the 38th International Colloquium on Automata, Languages and Programming (ICALP'11) . 330\u2013341. R. O'Donnell, J. Wright, and Y. Zhou. 2011. The fourier entropy-influence conjecture for certain classes of Boolean functions. In Proceedings of the 38th International Colloquium on Automata, Languages and Programming (ICALP'11). 330\u2013341."},{"key":"e_1_2_1_54_1","volume-title":"Proceedings of the 31st Conference on Computational Complexity (CCC'16)","author":"O'Donnell R.","unstructured":"R. O'Donnell and Y. Zhao . 2016. Polynomial bounds for decoupling, with applications . In Proceedings of the 31st Conference on Computational Complexity (CCC'16) . 24:1\u201324:18. R. O'Donnell and Y. Zhao. 2016. Polynomial bounds for decoupling, with applications. In Proceedings of the 31st Conference on Computational Complexity (CCC'16). 24:1\u201324:18."},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jmaa.2011.08.004"},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1142\/S0219199717500298"},{"key":"e_1_2_1_57_1","unstructured":"R. A. Servedio and E. Viola. 2012. On a special case of rigidity. Retrieved from http:\/\/eccc.hpi-web.de\/report\/2012\/144. R. A. Servedio and E. Viola. 2012. On a special case of rigidity. Retrieved from http:\/\/eccc.hpi-web.de\/report\/2012\/144."},{"key":"e_1_2_1_58_1","unstructured":"G. Shalev. 2018. On the Fourier Entropy Influence Conjecture for Extremal Classes. Retrieved from https:\/\/arxiv:1806.03646. G. Shalev. 2018. On the Fourier Entropy Influence Conjecture for Extremal Classes. Retrieved from https:\/\/arxiv:1806.03646."},{"key":"e_1_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.1137\/080735096"},{"key":"e_1_2_1_60_1","doi-asserted-by":"publisher","DOI":"10.1002\/j.1538-7305.1948.tb01338.x"},{"key":"e_1_2_1_61_1","doi-asserted-by":"publisher","DOI":"10.1145\/3188745.3188958"},{"key":"e_1_2_1_62_1","doi-asserted-by":"publisher","DOI":"10.1137\/080733644"},{"key":"e_1_2_1_63_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(00)00069-7"},{"key":"e_1_2_1_64_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2014.65"},{"key":"e_1_2_1_65_1","doi-asserted-by":"publisher","DOI":"10.5555\/3135595.3135610"},{"key":"e_1_2_1_66_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-02777-2_12"},{"key":"e_1_2_1_67_1","volume-title":"Proceedings of the 54th Annual IEEE Symposium on Foundations of Computer Science (FOCS'13)","author":"Tsang H. Y.","unstructured":"H. Y. Tsang , C. H. Wong , N. Xie , and S. Zhang . 2013. Fourier sparsity, spectral norm, and the log-rank conjecture . In Proceedings of the 54th Annual IEEE Symposium on Foundations of Computer Science (FOCS'13) . 658\u2013667. H. Y. Tsang, C. H. Wong, N. Xie, and S. Zhang. 2013. Fourier sparsity, spectral norm, and the log-rank conjecture. In Proceedings of the 54th Annual IEEE Symposium on Foundations of Computer Science (FOCS'13). 658\u2013667."},{"key":"e_1_2_1_68_1","volume-title":"Proceedings of the 5th Innovations in Theoretical Computer Science (ITCS'14)","author":"Wan A.","unstructured":"A. Wan , J. Wright , and C. Wu . 2014. Decision trees, protocols and the entropy-influence conjecture . In Proceedings of the 5th Innovations in Theoretical Computer Science (ITCS'14) . 67\u201380. A. Wan, J. Wright, and C. Wu. 2014. Decision trees, protocols and the entropy-influence conjecture. In Proceedings of the 5th Innovations in Theoretical Computer Science (ITCS'14). 67\u201380."},{"key":"e_1_2_1_69_1","first-page":"1","article-title":"A brief introduction to fourier analysis on the Boolean cube","volume":"1","author":"de Wolf R.","year":"2008","unstructured":"R. de Wolf . 2008 . A brief introduction to fourier analysis on the Boolean cube . Theory Comput. Library Grad. Surveys 1 (2008), 1 \u2013 20 . R. de Wolf. 2008. A brief introduction to fourier analysis on the Boolean cube. Theory Comput. Library Grad. Surveys 1 (2008), 1\u201320.","journal-title":"Theory Comput. Library Grad. Surveys"},{"key":"e_1_2_1_70_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973402.136"},{"key":"e_1_2_1_71_1","doi-asserted-by":"publisher","DOI":"10.5555\/2011781.2011786"}],"container-title":["ACM Transactions on Computation Theory"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3470860","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,1,2]],"date-time":"2023-01-02T01:51:54Z","timestamp":1672624314000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3470860"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,9]]},"references-count":71,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2021,12,31]]}},"alternative-id":["10.1145\/3470860"],"URL":"https:\/\/doi.org\/10.1145\/3470860","relation":{},"ISSN":["1942-3454","1942-3462"],"issn-type":[{"value":"1942-3454","type":"print"},{"value":"1942-3462","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,9]]},"assertion":[{"value":"2020-08-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-04-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-09-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}