AI summaryⓘ
The authors introduce a new measure called the subcube stifling number for Boolean functions, which captures how well a function can isolate any input pattern on a small subset of its variables by fixing the others. They connect this measure to the approximate degree of functions, showing that if a function’s approximate degree is roughly the square root of its subcube stifling number, then the approximate degree behaves nicely under composition. They provide results on typical values of this measure for random functions and for certain functions related to linear codes, and show that these code-related functions do not meet the ideal square-root approximate degree property. The key open question is whether any function exists that achieves the desired relation between approximate degree and subcube stifling number.
Boolean functionsubcube stifling numberapproximate degreefunction compositionpoint indicator functionrandom Boolean functionslinear codesminimum distancedual distancecombinatorial measure
Authors
Arjan Cornelissen, Nikhil S. Mande, Nithish Raja
Abstract
We introduce the subcube stifling number, a new combinatorial measure of total Boolean functions. This measure is the largest integer $k$ such that, for every set $S$ of at most $k$ input variables and every assignment $b \in \{0,1\}^S$, there is a fixing of the variables outside $S$ under which the resulting function on the free variables $S$ is the point indicator $\mathbb{I}[x_S=b]$. Equivalently, for every small set of coordinates, the function can isolate any prescribed point of the corresponding Boolean cube by suitably fixing all remaining coordinates. This measure is inspired by the stifling number of Chattopadhyay et al.~(ITCS'23); whereas their measure asks for restrictions realizing every constant function, ours asks for restrictions realizing every point indicator. Our results are as follows. 1) We show that the subcube stifling number gives rise to an approximate-degree composition theorem. In particular, if a Boolean function $f$ has approximate degree $O(\sqrt{μ(f)})$, then for every Boolean function $g$, approximate degree composes tightly. This motivates the study of the subcube stifling number, and in particular the search for functions whose approximate degree is $O(\sqrt{μ(f)})$. 2) We show that a random Boolean function on $n$ input bits has subcube stifling number $Θ(\log(n))$ with high probability. 3) We show that indicators of linear codes over $\mathbb{F}_2$ whose minimum distance and dual distance are both linear have high subcube stifling number. 4) We prove that the functions arising from this linear-code construction do not have approximate degree $O(\sqrt{μ(f)})$; in fact, they have approximate degree $Ω(μ(f))$. The main question left open is whether there exists a Boolean function $f$ with approximate degree $Θ(\sqrt{μ(f)})$. A positive answer would yield new instances of tight approximate-degree composition.