On a Boolean function without bold folding in the spectrum support and implications for greedy approaches to PDT depth
2026-07-06 • Computational Complexity
Computational Complexity
AI summaryⓘ
The authors study special rules for breaking down Boolean functions using parity decision trees (PDTs). They build on previous work showing that certain patterns in the function’s Fourier spectrum don’t overlap much under shifts. The authors create an explicit, neat family of functions with even less overlap, improving the earlier result. This shows that a natural greedy method to build PDTs, assuming maximum overlap behavior holds in all cases, can’t do better than a certain limit. However, since this assumption doesn't always hold, their work only rules out a simple greedy approach, leaving other strategies still possible.
Boolean functionsFourier spectrumparity decision treesFourier supportfolding directionsaffine subspace partitionAPLPS-partitionlinear spreadsgreedy algorithmsspectral methods
Authors
Yuriy Tarannikov
Abstract
We study Boolean functions and their Fourier spectrum supports in the context of parity decision trees (PDTs). Recently, H.~Hatami et al.~\cite{HHL+} constructed examples whose Fourier support \(\mathcal S\) satisfies $$ |(\mathcal S+γ_1)\cap(\mathcal S+γ_2)|=O(|\mathcal S|^{5/6}) $$ for all distinct \(γ_1,γ_2\), thereby refuting a natural greedy approach based on finding a single large folding direction. We strengthen this folding estimate by constructing an explicit infinite family of Boolean functions such that $$ |(\mathcal S+γ_1)\cap(\mathcal S+γ_2)|=O(|\mathcal S|^{1/2}) $$ for all distinct \(γ_1,γ_2\). The construction uses a special affine subspace partition, called an APLPS-partition, obtained from full linear spreads. In contrast with the probabilistic construction of \cite{HHL+}, our construction is explicit and has no background spectral components. We also discuss consequences for greedy approaches to PDT construction. Under the <<lazy>> assumption that the maximum-folding bound is inherited by all restrictions, the usual folding-counting argument cannot yield a PDT upper bound better than \(O(|\mathcal S|^{1/2})\), matching the known general upper bound. However, this inheritance assumption is false in general; hence our result refutes only this <<lazy>> maximum-folding approach, while a complete refutation of adaptive greedy strategies remains open.