Exact and point-wise approximating representations of Boolean functions by real polynomials have been of great interest in the theory of computing. We focus on the study of sparsity of such representations. Our results include the following:
- We show that for every total Boolean function, its exact and approximate sparsity in the De Morgan basis, are polynomially related to each other in the log scale, ignoring poly-log$(n)$ factors. This answers an open question posed by Knop, Lovett, McGuire and Yuan (STOC 2021). It builds on and is analogous to the seminal result of Nisan and Szegedy (Computational Complexity 1994) who proved the same for degree and approximate degree.
- We consider more powerful representations using generalized monomials, where each monomial is an indicator of a sub-cube. There are $3^n$ such monomials, where $n$ is the number of variables. We prove that even for these representations, the sparsity and approximate sparsity of total Boolean functions remain polynomially related to each other in the log scale, ignoring poly-log$(n)$ factors.
- We show that for every total Boolean function $f$, the log of its De Morgan sparsity characterizes upto polynomial loss and ingnoring poly-log$(n)$ factors, the quantum and classical 2-party bounded-error communication complexity of $f \circ EQ_4$, where $EQ_4$ is Equality of two 2-bit strings, one held by Alice and the other by Bob. As a consequence, we show that bounded-error quantum protocols cannot exhibit super-polynomial cost advantage over their classical counterparts, for computing such functions.
At the core of all our results, lies a novel characterization of non-sparse functions. This characterization is in terms of a combinatorial object that we call max-degree restriction trees. These objects locally certify high sparsity, in the same sense that block-sensitivity locally certifies degree.
This work subsumes our earlier ECCC report, Exact versus Approximate Representations of Boolean Functions in the De Morgan Basis (https://eccc.weizmann.ac.il/report/2025/101/), except for a single result on monotone functions; all other results are strengthened or extended here.
