Read-once formulas and a question of Han on the Fourier entropy-influence conjecture

For a Boolean function $f$ and a coordinate $k$, let $Q_k(f)=\sum_{S\not\ni k}|\hat f(S)\hat f(S\cup\{k\})|/I_k(f)$, where $I_k(f)$ is the influence of $k$. In his proof of a new bound towards the Fourier entropy-influence conjecture, Han asked whether there is a universal constant $c$ such that every Boolean function has a coordinate $k$ with $Q_k(f)\le c$, and observed that this would imply the conjecture. We show that the answer is negative. For balanced alternating read-once AND-OR formulas we compute $Q_k$ exactly by a one-step recursion over the levels of the formula; it is the same at every coordinate. Choosing the fan-ins so that every gate below the root is true with probability at most $1/4$ gives monotone read-once formulas of depth $L$ on at most $2\cdot 7^{L-1}$ variables with $Q_k(f)\ge L$ for every $k$, so $\min_k Q_k(f)$ grows at least like $\log_2 n/\log_2 7$. Depth two gives the tribes functions, for which $\min_k Q_k$ approaches $4$ but stays below it. The Fourier entropy-influence conjecture is known for these formulas, so the inequality in Han's question fails on a class where the conjecture holds. By contrast, the drop of the Fourier entropy under splitting on a coordinate is less than $5+\ln 4$ times the influence of that coordinate, for every read-once formula and every coordinate.

Authors

Institutions

Publication Details

Journal
Zenodo (CERN European Organization for Nuclear Research)
Published
2026-11-08
DOI
https://doi.org/10.5281/zenodo.24064348
Primary Topic
Complexity and Algorithms in Graphs
Type
preprint
Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
NOV
preprint

Read-once formulas and a question of Han on the Fourier entropy-influence conjecture

Yitzchak Shmalo
1 links
Zenodo (CERN European Organization for Nuclear Research)
Complexity and Algorithms in Graphs
preprint

Read-once formulas and a question of Han on the Fourier entropy-influence conjecture

Yitzchak Shmalo
preprint en

Abstract

For a Boolean function $f$ and a coordinate $k$, let $Q_k(f)=\sum_{S\not\ni k}|\hat f(S)\hat f(S\cup\{k\})|/I_k(f)$, where $I_k(f)$ is the influence of $k$. In his proof of a new bound towards the Fourier entropy-influence conjecture, Han asked whether there is a universal constant $c$ such that every Boolean function has a coordinate $k$ with $Q_k(f)\le c$, and observed that this would imply the conjecture. We show that the answer is negative. For balanced alternating read-once AND-OR formulas we compute $Q_k$ exactly by a one-step recursion over the levels of the formula; it is the same at every coordinate. Choosing the fan-ins so that every gate below the root is true with probability at most $1/4$ gives monotone read-once formulas of depth $L$ on at most $2\cdot 7^{L-1}$ variables with $Q_k(f)\ge L$ for every $k$, so $\min_k Q_k(f)$ grows at least like $\log_2 n/\log_2 7$. Depth two gives the tribes functions, for which $\min_k Q_k$ approaches $4$ but stays below it. The Fourier entropy-influence conjecture is known for these formulas, so the inequality in Han's question fails on a class where the conjecture holds. By contrast, the drop of the Fourier entropy under splitting on a coordinate is less than $5+\ln 4$ times the influence of that coordinate, for every read-once formula and every coordinate.

Zenodo (CERN European Organization for Nuclear Research)
Hebrew University of Jerusalem (IL)
Complexity and Algorithms in Graphs
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.

Laika access coming soon
Read-once formulas and a question of Han on the Fourier entropy-influence conjecture — Yitzchak Shmalo · Zenodo (CERN European Organization for Nuclear Research) (2026) | TGRS Research Map | TGRS