错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

A New Bound for the Fourier-Entropy-Influence Conjecture

  • Xiao Han

摘要

In this paper, we prove that the Fourier entropy of an n-dimensional boolean function f can be upper-bounded by \(O(I(f)+ \sum \limits _{k\in [n]}I_k(f)\log \frac{1}{I_k(f)})\) O ( I ( f ) + k [ n ] I k ( f ) log 1 I k ( f ) ) , where I(f) is its total influence and \(I_k(f)\) I k ( f ) is the influence of the k-th coordinate. There is no strict quantitative relationship between our bound with the known bounds for the Fourier-Min-Entropy-Influence conjecture \(O(I(f)\log I(f))\) O ( I ( f ) log I ( f ) ) and \(O(I(f)^2)\) O ( I ( f ) 2 ) . The proof is elementary and uses iterative bounds on moments of Fourier coefficients over different levels to estimate the Fourier entropy as its derivative.