Fourier entropy influence conjecture holds for plateaued Boolean functions
On the Fourier Entropy-Influence Conjecture for Boolean Plateaued Functions
Information Theory
Summary
The paper deals with a mathematical property of special functions called Boolean plateaued functions, which arise in computer science and coding theory. The authors prove an inequality related to these functions that confirms a longstanding open question, the Fourier Entropy-Influence conjecture, in this specific case. They also find exact values for constants that measure the complexity of these functions. Additionally, their work extends to related functions and different probability distributions on binary inputs.
What this means in practice
- •For coding theorists: Determine precise complexity measures for certain Reed-Muller codewords related to plateaued Boolean functions.
- •For cryptographic function designers: Use confirmed bounds on complexity measures for plateaued and partially bent functions when designing cryptographic primitives.
A theory result. No direct application yet.
Authors
Vladimir N. Potapov
Abstract
We prove the following inequality for Boolean functions: $2\sum_{x\in F_2^n}f(x)wt(x)\geq wt(f)(n-deg(f))$. Using this inequality, we establish the Fourier Entropy-Influence (FEI) conjecture for Boolean plateaued functions. In particular, we show that the sharp FEI constant for the class of plateaued functions is 4. We also prove the FEI conjecture for partially bent functions and show that the corresponding sharp constant is 2. Finally, we derive several estimates for the p-biased distribution on the Boolean hypercube. Keywords: Fourier entropy, total influence, average sensitivity, plateaued function, algebraic degree, Reed-Muller code, p-biased distribution.