A halfspace, or linear threshold function (LTF), outputs the sign of a weighted sum of its $\pm1$ inputs minus a threshold. It is the simplest nonlinear Boolean classifier, yet no one has proved that its Fourier spectrum is as concentrated as a long-standing conjecture predicts. Every Boolean function has a Fourier spectrum, which expands it into parities (products of subsets of inputs). The squared coefficients sum to one, so they form a probability distribution. The Fourier Entropy-Influence (FEI) conjecture of Friedgut and Kalai says that the entropy of this distribution is at most a universal constant times the function's total influence, meaning the expected number of input bits whose flip changes the output. Chakraborty et al. proved FEI for random LTFs. Their argument pairs a crude $O(\sqrt n)$ entropy bound with a proof that random weights force influence $\Omega(\sqrt n)$. They name the deterministic case, with skewed or adversarial weights, as the open problem. Skewed weights can push influence far below $\sqrt n$, and then their comparison breaks.
We propose to prove FEI for all LTFs by peeling off heavy coordinates one at a time. Fixing an input bit of an LTF does not create a new kind of function. It gives back the same halfspace with its threshold shifted by twice that bit's weight. We aim to prove a chain rule: each time a heavy coordinate is fixed, the Fourier entropy rises by at most a constant times that coordinate's influence. Influence already splits exactly over such restrictions. The chain rule would therefore reduce FEI for any LTF to FEI for its "regular" pieces, where no weight dominates. There a weighted version of the random-LTF argument can apply. Choosing which coordinates to peel follows the critical-index head/tail split from derandomization work. Very skewed, exponentially weighted halfspaces (the hard end of the weight-degree tradeoff) end up entirely in the peeled head.
Core Claim
Let $f$ be an LTF, let $i$ be a coordinate, and let $f_{+}, f_{-}$ be $f$ with $x_i$ fixed to $+1$ and $-1$. Write $H(\cdot)$ for Fourier entropy and $\mathrm{Inf}_i[f]$ for the probability that flipping bit $i$ changes $f$. Total influence satisfies the exact identity $\mathbf I[f] = \mathrm{Inf}_i[f] + \tfrac12\mathbf I[f_+] + \tfrac12\mathbf I[f_-]$. We define the restriction excess $\Delta_i$ by
$$H(\widehat f^{\,2}) \;=\; \tfrac12 H(\widehat{f_+}^{\,2}) + \tfrac12 H(\widehat{f_-}^{\,2}) + \Delta_i(f).$$
Suppose $\Delta_i(f) \le C\,\mathrm{Inf}_i[f]$ at every internal node of a decision tree, and every leaf satisfies $H \le C\,\mathbf I$. Then $f$ satisfies FEI with constant $C$, by induction up the tree.
This cannot hold for arbitrary functions and arbitrary coordinates. If it did, querying all $n$ bits would leave constant leaves, and FEI would follow for every Boolean function. The claim is therefore specifically about LTFs. It rests on one structural fact: for an LTF, $f_+ \ge f_-$ pointwise, because both are the same halfspace with thresholds $2w_i$ apart. So $f_+ - f_-$ is a nonnegative indicator of a "slab" of inputs.
We conjecture the bound $\Delta_i \le C\,\mathrm{Inf}_i$ holds whenever $|w_i|$ is large compared with the norm of the remaining tail weights, which is exactly the head of the critical-index decomposition. We expect it to fail for low-weight tail coordinates. At those, a tiny influence can reshuffle many small Fourier coefficients.
The accounting splits $\Delta_i$ into two pieces. The first is a within-subset rotation term. For each subset $S$ not containing $i$, the mass at $S$ in the averaged restrictions is redistributed between $S$ and $S\cup\{i\}$. By concavity of binary entropy this term is at most $h(\mathrm{Inf}_i)$. That already gives a constant times $\mathrm{Inf}_i$ up to a $\log(1/\mathrm{Inf}_i)$ factor.
The second is a mixing term: the Jensen-Shannon divergence between the spectra of $f_+$ and $f_-$. The generic bound on it scales like $\sqrt{\mathrm{Inf}_i}$, which is far too large. The mathematical core of the project is to show that when $f_+ - f_-$ is a slab of a heavy-weight shift, the two spectra are close in divergence at rate $O(\mathrm{Inf}_i)$ rather than $O(\sqrt{\mathrm{Inf}_i})$. Removing the residual $\log(1/\mathrm{Inf}_i)$ from the first term is a secondary target.
Research Program
The first component is the chain-rule lemma for head coordinates. We will state it relative to the critical index of Bounded Independence Fools Halfspaces, which orders weights by magnitude and marks where the remaining tail becomes $\tau$-regular. That paper supplies the partition. We supply the entropy bookkeeping, which it never needed.
There is a structural boundary case. When every head weight exceeds the sum of all remaining weights, the head computes a decision list, such as the ODD-MAX-BIT function. Decision lists are read-once formulas with bounded-arity gates. For those, O'Donnell and Tan's composition theorem already proves FEI. Our lemma must reproduce that case, which serves as a consistency check. It must also go beyond it to heads whose weights decay geometrically without strictly dominating the rest. Those heads are no longer read-once, and the composition theorem does not reach them.
The second component is FEI for regular LTFs with arbitrary thresholds and uneven weights. Here the Chakraborty et al. comparison fails for a different reason. Their global $O(\sqrt n)$ entropy bound does not track influence. For a $\tau$-regular LTF, influence behaves like $\|w\|_1/\|w\|_2$ times a Gaussian density factor at the normalized threshold. That quantity can be much smaller than $\sqrt n$ when weights are uneven or the threshold is large.
We will aim for an entropy bound of the same weighted form, first up to a $\log(1/\tau)$ factor. The tools are the Berry-Esseen control those authors use and the level-by-level Fourier tail bounds from Degree and Sensitivity. The critical-index recursion of Diakonikolas and Servedio ensures the head has depth depending only on $\tau$, or else the function is already close to a head junta. Either way, the tree is shallow enough for the induction.
A third component is exploratory. For degree-2 polynomial threshold functions (PTFs), fixing a variable changes the polynomial's linear part, not just its threshold. Pointwise monotonicity of $f_+ - f_-$ is therefore lost. We will measure numerically whether the chain rule survives on the heavy coordinates selected by the Diakonikolas-Servedio-Tan regularity lemma. This tells us whether the method has any route to PTFs. Harsha, Klivans, and Meka and Kane bound PTF influence but never touch entropy.
The weight-degree direction plays a specific role in this program. Exact integer weights up to $2^{\Omega(n\log n)}$ are what create skewed heads. The tradeoff literature, for example Servedio, Tan, and Thaler, predicts that the hard instances are decision-list-like. We will therefore stratify all experiments by minimal integer weight. The goal is to test whether the entropy-to-influence ratio worsens as weight grows, or whether large weight only enlarges the head that the chain rule handles.
Baselines
The naive reference point is the general bound $H(\widehat f^{\,2}) = O(\mathbf I[f]\log s(f))$ from Degree and Sensitivity, where $s(f)$ is the maximum over inputs of the number of sensitive bits. It already holds for every LTF. For LTFs like majority, $s(f)$ is linear in $n$, so it proves FEI only up to a $\log n$ loss. Beating it means a constant independent of $n$.
The strongest existing method is the sandwich argument of Chakraborty et al.. It is the only LTF-specific FEI result in the file, and it covers random Gaussian or uniform weights with high probability. The file gives no explicit constant for it: no reported result found on Lacuna for an explicit FEI constant for LTFs. The only numerical anchor is O'Donnell and Tan's general lower bound $C \ge 6.278$ on the universal FEI constant. We will run that argument's ingredients on the same weight families we test. Beating it means a proof, or empirical evidence at exhaustive small $n$, that covers deterministic skewed weights, where the sandwich provably collapses.
We will also compare against the certificate bound $H \le 2\,\mathrm{aUC}^{\oplus}(f)$ of Srinivasan et al., evaluated on the same exhaustively enumerated LTFs.
The key ablation isolates the threshold-shift structure. We will compute $\Delta_i/\mathrm{Inf}_i$ in three settings: head coordinates of LTFs, tail coordinates of LTFs, and coordinates of non-unate functions matched in influence. If the ratio is bounded in the first setting only, the critical-index choice and the LTF structure are both doing real work. If it is bounded everywhere, something is wrong, because that would contradict the observation that a general chain rule implies FEI for all functions.
Why not just…?
Why not just accept the $O(\mathbf I\log s)$ bound? It is a real result and holds today. But the $\log s$ factor is exactly the gap between "entropy is controlled by influence" and "entropy is controlled by influence and dimension." Majority-like LTFs have $s$ linear in $n$, so the loss is unavoidable in that method. Our exhaustive experiments will show whether the true ratio stays bounded in $n$ on these functions, which is what makes removing the log factor worth attempting.
Why not just bound entropy by certificate complexity? The Srinivasan et al. bound $H \le 2\,\mathrm{aUC}^{\oplus}(f)$ is tight for some classes. For balanced LTFs, however, unambiguous certificates must fix about half the inputs, while influence is only order $\sqrt n$. Certificate measures ignore the anti-concentration that regularity captures. We will report both quantities side by side on enumerated LTFs.
Why not just replace $f$ by its low-weight approximator and analyze that? The $\sqrt n\,(1/\epsilon)^{O(\log^2(1/\epsilon))}$ weight approximators of Diakonikolas and Servedio are close to $f$ in Hamming distance. Fourier entropy, however, is not stable under small $L_2$ perturbations. An $\epsilon$ change can spread mass over exponentially many tiny coefficients and add entropy far exceeding $\epsilon$ times influence. We will measure this directly by computing entropy for pairs of a function and its low-weight approximation. A small gap would make this route a genuine competitor for FEI up to additive error, though it could still not give the exact inequality.
Why not just run the chain rule over a full decision tree for any function? That would prove FEI for all Boolean functions. Any per-query lemma must therefore use structure. The ablation above tests whether the threshold-shift structure is sufficient on head coordinates, and whether it is insufficient on tail coordinates, as we predict.
Proposed Experiments
We will compute exact Fourier spectra with the fast Walsh-Hadamard transform for $n \le 26$. We will also enumerate all threshold functions up to $n = 9$ by integer weight vectors, which gives exhaustive coverage of the skewed regime at small size. The weight families are:
- Gaussian and uniform random weights, the Chakraborty et al. regime.
- Geometric weights at several decay rates, covering ODD-MAX-BIT-like and intermediate heads.
- Planted head-plus-regular-tail constructions.
- Weights from adversarial hill-climbing that maximizes $H/\mathbf I$ over weights and threshold.
The metrics are the worst-case $H/\mathbf I$ ratio per $n$ and per integer-weight stratum, the distribution of $\Delta_i/\mathrm{Inf}_i$ for head versus tail coordinates, and the regular-leaf ratio against the weighted $\|w\|_1/\|w\|_2$ prediction.
The decisive checks are these. If exhaustive enumeration finds a head coordinate with $\Delta_i/\mathrm{Inf}_i$ growing with $n$ or with weight, the chain-rule approach is dead and we report the counterexample family. If $\Delta_i/\mathrm{Inf}_i$ stays bounded on heads but diverges on tails, the proof strategy is confirmed. The remaining work is then the regular-leaf bound, checked against adversarial regular instances. If the adversarial search pushes the LTF ratio toward or above 6.278, that is itself a notable finding: it would place halfspaces among the hardest known FEI instances. The degree-2 PTF runs report the same head/tail statistics. They decide whether a follow-up on polynomial threshold functions is warranted.
References
- Fourier Entropy-Influence Conjecture for Random Linear Threshold Functions
- Bounded Independence Fools Halfspaces
- A Composition Theorem for the Fourier Entropy-Influence Conjecture
- Degree and Sensitivity: Tails of Two Distributions
- Nearly optimal solutions for the chow parameters problem and low-weight approximation of halfspaces
- A Regularity Lemma and Low-Weight Approximators for Low-Degree Polynomial Threshold Functions
- Bounding the Sensitivity of Polynomial Threshold Functions
- The Correct Exponent for the Gotsman-Linial Conjecture
- Attribute-Efficient Learning and Weight-Degree Tradeoffs for Polynomial Threshold Functions
- Improved Bounds on Fourier Entropy and Min-Entropy.