Document Open Access Logo

Improved Bounds on Fourier Entropy and Min-Entropy

Authors Srinivasan Arunachalam, Sourav Chakraborty, Michal Koucký, Nitin Saurabh, Ronald de Wolf

PDF
Thumbnail PDF

File

LIPIcs.STACS.2020.45.pdf
  • Filesize: 0.59 MB
  • 19 pages

Document Identifiers

Author Details

Srinivasan Arunachalam
  • MIT, Cambridge, MA, USA
Sourav Chakraborty
  • Indian Statistical Institute, Kolkata, India
Michal Koucký
  • Computer Science Institute of Charles University, Prague, Czech Republic
Nitin Saurabh
  • Max Planck Institut für Informatik, Saarland Informatics Campus, Saarbrücken, Germany
Ronald de Wolf
  • QuSoft, CWI and University of Amsterdam, the Netherlands

Funding

  • Arunachalam, Srinivasan: Work done when at QuSoft, CWI, Amsterdam, supported by ERC Consolidator Grant 615307 QPROGRESS and MIT-IBM Watson AI Lab under the project Machine Learning in Hilbert space.
  • Koucký, Michal: Partially supported by ERC Consolidator Grant 616787 LBCAD, and GAČR grant 19-27871X.
  • Saurabh, Nitin: Part of the work was done when the author was at IUUK, Prague and supported by the European Union’s Seventh Framework Programme (FP/2007-2013)/ERC Grant Agreement no. 616787.
  • de Wolf, Ronald: Partially supported by ERC Consolidator Grant 615307 QPROGRESS (ended Feb 2019) and by NWO under QuantERA project QuantAlgo 680-91-034 and the Quantum Software Consortium.

Acknowledgements

Part of this work was carried out when NS and SC visited CWI, Amsterdam and SA was part of MIT (supported by MIT-IBM Watson AI Lab under the project Machine Learning in Hilbert Space) and University of Bristol (partially supported by EPSRC grant EP/L021005/1). SA thanks Ashley Montanaro for his hospitality. NS and SC would like to thank Satya Lokam for many helpful discussions on the Fourier entropy-Influence conjecture. SA and SC thank Jop Briët for pointing us to the literature on unbalancing lights and many useful discussions regarding Section 3.3. We also thank Penghui Yao and Avishay Tal for discussions during the course of this project, and Fernando Vieira Costa Júnior for pointing us to the reference [F. Bayart et al., 2014]. Finally, we thank the anonymous reviewers for many helpful comments.

Cite AsGet BibTex

Srinivasan Arunachalam, Sourav Chakraborty, Michal Koucký, Nitin Saurabh, and Ronald de Wolf. Improved Bounds on Fourier Entropy and Min-Entropy. In 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 154, pp. 45:1-45:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
https://doi.org/10.4230/LIPIcs.STACS.2020.45

Abstract

Given a Boolean function f:{-1,1}ⁿ→ {-1,1}, define the Fourier distribution to be the distribution on subsets of [n], where each S ⊆ [n] is sampled with probability f̂(S)². The Fourier Entropy-Influence (FEI) conjecture of Friedgut and Kalai [E. Friedgut and G. Kalai, 1996] seeks to relate two fundamental measures associated with the Fourier distribution: does there exist a universal constant C>0 such that ℍ(f̂²)≤ C⋅ Inf(f), where ℍ(f̂²) is the Shannon entropy of the Fourier distribution of f and Inf(f) is the total influence of f? In this paper we present three new contributions towards the FEI conjecture: ii) Our first contribution shows that ℍ(f̂²) ≤ 2⋅ aUC^⊕(f), where aUC^⊕(f) is the average unambiguous parity-certificate complexity of f. This improves upon several bounds shown by Chakraborty et al. [S. Chakraborty et al., 2016]. We further improve this bound for unambiguous DNFs. iii) We next consider the weaker Fourier Min-entropy-Influence (FMEI) conjecture posed by O'Donnell and others [R. O'Donnell et al., 2011; R. O'Donnell, 2014] which asks if ℍ_{∞}(f̂²) ≤ C⋅ Inf(f), where ℍ_{∞}(f̂²) is the min-entropy of the Fourier distribution. We show ℍ_{∞}(f̂²) ≤ 2⋅?_{min}^⊕(f), where ?_{min}^⊕(f) is the minimum parity certificate complexity of f. We also show that for all ε ≥ 0, we have ℍ_{∞}(f̂²) ≤ 2log (‖f̂‖_{1,ε}/(1-ε)), where ‖f̂‖_{1,ε} is the approximate spectral norm of f. As a corollary, we verify the FMEI conjecture for the class of read-k DNFs (for constant k). iv) 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 flat polynomial (whose non-zero Fourier coefficients have the same magnitude) of degree d and sparsity 2^ω(d) 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.

Subject Classification

ACM Subject Classification
  • Computing methodologies → Representation of Boolean functions
  • Theory of computation → Models of computation
  • Mathematics of computing → Information theory
Keywords
  • Fourier analysis of Boolean functions
  • FEI conjecture
  • query complexity
  • polynomial approximation
  • approximate degree
  • certificate complexity

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. S. Aaronson and A. Ambainis. Forrelation: A problem that optimally separates quantum from classical computing. SIAM Journal of Computing, 47(3):982-1038, 2018. Earlier in STOC'15. URL: http://arxiv.org/abs/1411.5729.
  2. A. Akavia, A. Bogdanov, S. Guo, A.Kamath, and A.Rosen. Candidate weak pseudorandom functions in AC⁰∘MOD2. In Proceedings of the 5th Conference on Innovations in Theoretical Computer Science, ITCS'14, pages 251-260. ACM, 2014. Google Scholar
  3. N. Albuquerque, F. Bayart, D. Pellegrino, and J. B. Seoane-Sepúlveda. Sharp generalizations of the multilinear Bohnenblust-Hille inequality. Journal of Functional Analysis, 266(6):3276-3740, 2014. URL: http://arxiv.org/abs/1306.3362.
  4. A. Ambainis, M. Kokainis, and R. Kothari. Nearly optimal separations between communication (or query) complexity and partitions. In 31st Conference on Computational Complexity, CCC 2016, pages 4:1-4:14, 2016. Combines https://arxiv.org/abs/1512.01210 and https://arxiv.org/abs/1512.00661. Google Scholar
  5. S. Arunachalam, S. Chakraborty, M. Koucký, N. Saurabh, and R. de Wolf. Improved bounds on fourier entropy and min-entropy, 2018. URL: http://arxiv.org/abs/1809.09819.
  6. F. Bayart, D. Pellegrino, and J. B. Seoane-Sepúlveda. The Bohr radius of the n-dimensional polydisk is equivalent to √(logn)/n. Advances in Mathematics, 264:726-746, 2014. Google Scholar
  7. R. Beals, H. Buhrman, R. Cleve, M. Mosca, and R. de Wolf. Quantum lower bounds by polynomials. Journal of the ACM, 48(4):778-797, 2001. Earlier version in FOCS'98. URL: http://arxiv.org/abs/quant-ph/9802049.
  8. S. Ben-David, P. Hatami, and A. Tal. Low-sensitivity functions from unambiguous certificates. In 8th Innovations in Theoretical Computer Science Conference, ITCS 2017, pages 28:1-28:23, 2017. URL: http://arxiv.org/abs/1605.07084.
  9. H. F. Bohnenblust and E. Hille. On the absolute convergence of Dirichlet series. Annals of Mathematics, pages 600-622, 1931. Google Scholar
  10. R. Boppana. The average sensitivity of bounded-depth circuits. Information Processing Letters, 63(5):257-261, 1997. Google Scholar
  11. J. Bourgain and G. Kalai. Influences of variables and threshold intervals under group symmetries. Geometric and Functional Analysis (GAFA), 7(3):438-461, 1997. Google Scholar
  12. J. Briët, H. Buhrman, T. Lee, and T. Vidick. Multipartite entanglement in XOR games. Quantum Information & Computation, 13(3-4):334-360, 2013. URL: http://arxiv.org/abs/0911.4007.
  13. H. Buhrman and R. de Wolf. Complexity measures and decision tree complexity: A survey. Theoretical Computer Science, 288(1):21-43, 2002. Google Scholar
  14. S. Chakraborty, A. Chattopadhyay, N. Mande, and M. Paraashar. Quantum Query-to-Communication simulation needs a logarithmic overhead, 2019. URL: http://arxiv.org/abs/1909.10428.
  15. S. Chakraborty, S. Karmalkar, S. Kundu, S. V. Lokam, and N. Saurabh. Fourier entropy-influence conjecture for random linear threshold functions. In LATIN 2018: Theoretical Informatics - 13th Latin American Symposium, 2018, pages 275-289, 2018. Google Scholar
  16. S. Chakraborty, R. Kulkarni, S.V. Lokam, and N. Saurabh. Upper bounds on Fourier entropy. Theoretical Computer Science, 654:92-112, 2016. The first version appeared as a technical report TR13-052 on ECCC in 2013. Google Scholar
  17. M. Cheraghchi, E. Grigorescu, B. Juba, K. Wimmer, and N. Xie. AC⁰ ∘ MOD2 lower bounds for the Boolean inner product. Journal of Computer and System Sciences, 97:45-59, 2018. Google Scholar
  18. G. Cohen and I. Shinkar. The complexity of DNF of parities. In Proceedings of the 2016 ACM Conference on Innovations in Theoretical Computer Science, ITCS '16, pages 47-58. ACM, 2016. Google Scholar
  19. T. M. Cover and J. A. Thomas. Elements of Information Theory. John Wiley & Sons, 1991. Google Scholar
  20. B. Das, M. Pal, and V. Visavaliya. The entropy influence conjecture revisited, 2011. URL: http://arxiv.org/abs/1110.4301.
  21. A. Defant, L. Frerick, J. Ortega-Cerdá, M. Ounaïes, and K. Seip. The Bohnenblust-Hille inequality for homogeneous polynomials is hypercontractive. Annals of Mathematics, 174(1):485-497, 2011. URL: http://arxiv.org/abs/0904.3540.
  22. A. Defant, D. Popa, and U. Schwarting. Coordinatewise multiple summing operators in banach spaces. Journal of Functional Analysis, 259(1):220-242, 2010. Google Scholar
  23. E. Friedgut. Boolean functions with low average sensitivity depend on few coordinates. Combinatorica, 18(1):27-35, 1998. Google Scholar
  24. E. Friedgut and G. Kalai. Every monotone graph property has a sharp threshold. Proceedings of the American Mathematical Society, 124(10):2993-3002, 1996. Google Scholar
  25. M. Göös. Lower bounds for clique vs. independent set. In IEEE 56th Annual Symposium on Foundations of Computer Science, FOCS 2015, pages 1066-1076, 2015. Google Scholar
  26. P. Gopalan, A. T. Kalai, and A. Klivans. Agnostically learning decision trees. In Proceedings of the 40th annual ACM symposium on Theory of computing, STOC '08, pages 527-536, 2008. Google Scholar
  27. P. Gopalan, R. A. Servedio, A. Tal, and A. Wigderson. Degree and sensitivity: Tails of two distributions. In 31st Conference on Computational Complexity, CCC 2016, pages 13:1-13:23, 2016. URL: http://arxiv.org/abs/1604.07432.
  28. L. Gross. Logarithmic Sobolev inequalities. American Journal of Mathematics, 97(4):1061-1083, 1975. Google Scholar
  29. R. Hod. Improved lower bounds for the Fourier entropy/influence conjecture via lexicographic functions, 2017. URL: http://arxiv.org/abs/1711.00762.
  30. J. Kahn, G. Kalai, and Nathan Linial. The influence of variables on Boolean functions. In Proceedings of the 29th Annual IEEE Symposium on Foundations of Computer Science, pages 68-80, 1988. Google Scholar
  31. G. Kalai. The entropy/influence conjecture. Terence Tao’s blog: https://terrytao.wordpress.com/2007/08/16/gil-kalai-the-entropyinfluence-conjecture/, 2007. URL: https://terrytao.wordpress.com/2007/08/16/gil-kalai-the-entropyinfluence-conjecture/.
  32. N. Keller, E. Mossel, and T. Schlank. A note on the entropy/influence conjecture. Discrete Mathematics, 312(22):3364-3372, 2012. URL: http://arxiv.org/abs/1105.2651.
  33. A. Klivans, H. Lee, and A. Wan. Mansour’s conjecture is true for random DNF formulas. In Proceedings of the 23rd Conference on Learning Theory, pages 368-380, 2010. Google Scholar
  34. T. Lee and A. Shraibman. Lower bounds in communication complexity. Foundations and Trends in Theoretical Computer Science, 3(4):263-398, 2009. Google Scholar
  35. N. Linial, Y. Mansour, and N. Nisan. Constant depth circuits, fourier transform, and learnability. J. ACM, 40(3):607-620, July 1993. Google Scholar
  36. J. E. Littlewood. On bounded bilinear forms in an infinite number of variables. The Quarterly Journal of Mathematics, 1:164-174, 1930. Google Scholar
  37. Y. Mansour. An n^O(log log n) learning algorithm for DNF under the uniform distribution. Journal of Computer and System Sciences, 50(3):543-550, 1995. Google Scholar
  38. A. Montanaro. Some applications of hypercontractive inequalities in quantum information theory. Journal of Mathematical Physics, 53(12):122206, 2012. URL: http://arxiv.org/abs/1208.0161.
  39. A. Montanaro and T. Osborne. On the communication complexity of XOR functions, 2009. URL: http://arxiv.org/abs/0909.3392.
  40. R. O'Donnell. Analysis of Boolean Functions. Cambridge University Press, 2014. Google Scholar
  41. R. O'Donnell and L-Y. Tan. A composition theorem for the Fourier entropy-influence conjecture. In Proceedings of Automata, Languages and Programming - 40th International Colloquium, pages 780-791, 2013. URL: http://arxiv.org/abs/1304.1347.
  42. R. O'Donnell, J. Wright, Y. Zhao, X. Sun, and L-Y. Tan. A composition theorem for parity kill number. In IEEE 29th Conference on Computational Complexity, CCC 2014, pages 144-154, 2014. URL: http://arxiv.org/abs/1312.2143.
  43. R. O'Donnell, J. Wright, and Y. Zhou. The Fourier entropy-influence conjecture for certain classes of Boolean functions. In Proceedings of Automata, Languages and Programming - 38th International Colloquium, pages 330-341, 2011. Google Scholar
  44. R. O'Donnell and Y. Zhao. Polynomial bounds for decoupling, with applications. In 31st Conference on Computational Complexity, CCC 2016, pages 24:1-24:18, 2016. URL: http://arxiv.org/abs/1512.01603.
  45. D. Pellegrino and E. V. Teixeira. Towards sharp Bohnenblust-Hille constants. Communications in Contemporary Mathematics, 20(3):1750029, 2018. URL: http://arxiv.org/abs/1604.07595.
  46. R. A. Servedio and E. Viola. On a special case of rigidity. Manuscript: http://eccc.hpi-web.de/report/2012/144, 2012. URL: http://eccc.hpi-web.de/report/2012/144.
  47. G. Shalev. On the Fourier Entropy Influence conjecture for extremal classes. arXiv, 2018. URL: http://arxiv.org/abs/1806.03646.
  48. R. Shaltiel and E. Viola. Hardness amplification proofs require majority. SIAM Journal on Computing, 39(7):3122-3154, 2010. Google Scholar
  49. C. E. Shannon. A mathematical theory of communication. Bell System Technical Journal, 27(3):379-423, 1948. Google Scholar
  50. Alexander A. Sherstov. Algorithmic polynomials. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2018, Los Angeles, CA, USA, June 25-29, 2018, pages 311-324, 2018. Google Scholar
  51. A. Tal. Tight bounds on the Fourier spectrum of AC⁰. In 32nd Computational Complexity Conference, CCC 2017, pages 15:1-15:31, 2017. Google Scholar
  52. H. Y. Tsang, C. H. Wong, N. Xie, and S. Zhang. Fourier sparsity, spectral norm, and the log-rank conjecture. In 54th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2013, pages 658-667, 2013. URL: http://arxiv.org/abs/1304.1245.
  53. A. Wan, J. Wright, and C. Wu. Decision trees, protocols and the entropy-influence conjecture. In Innovations in Theoretical Computer Science, ITCS'14, pages 67-80, 2014. URL: http://arxiv.org/abs/1312.3003.
  54. R. de Wolf. A brief introduction to Fourier analysis on the Boolean cube. Theory of Computing, 2008. ToC Library, Graduate Surveys 1. Google Scholar
  55. S. Zhang. Efficient quantum protocols for XOR functions. In Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014, pages 1878-1885, 2014. URL: http://arxiv.org/abs/1307.6738.
  56. Z. Zhang and Y. Shi. Communication complexities of symmetric XOR functions. Quantum Information & Computation, 9(3):255-263, 2009. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact