Erasure entropies of sparse linear DNFs
For a Boolean function $f$ and a coordinate $i$, the erasure entropy $E_i(f)$ is the conditional entropy of the event $i\in U$ given $U\setminus\{i\}$, where $U$ is drawn from the spectral distribution $\hat f^2$. The Fourier entropy-influence conjecture is equivalent to every non-constant $f$ having a coordinate with $E_i(f)=O(\mathrm{Inf}_i(f))$. We consider monotone DNFs whose terms all have width $w$, any two of which share at most one variable, and in which every variable lies in at most $D$ terms. We show that $E_i(f)/\mathrm{Inf}_i(f)=2+o(1)$ at every relevant coordinate, uniformly in the number of variables and terms, as $w\to\infty$ with $D\le2^{(1-\eta)(w-1)}$ for a fixed $\eta>0$, and we give an explicit error bound for each $w$, $D$ and degree of $i$. The proof rests on a separation inequality valid for every monotone function: if the derivative $D_if$ puts little spectral weight outside a family $\Omega$ of sets and the restriction $f|_{x_i=0}$ puts little weight on $\Omega$, then $E_i/\mathrm{Inf}_i$ is close to $2$. For a linear DNF, $\Omega$ is the family of sets that contain many of the other variables of some term through $i$.
Authors
- Yitzchak Shmalo (ORCID: https://orcid.org/0000-0002-2886-3049)
Institutions
- Hebrew University of Jerusalem (IL)
Publication Details
- Journal
- Zenodo (CERN European Organization for Nuclear Research)
- Published
- 2026-11-11
- DOI
- https://doi.org/10.5281/zenodo.24125386
- Primary Topic
- Complexity and Algorithms in Graphs
- Type
- preprint