Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2607.04850

Subcube Stifling

Arjan Cornelissen, Nikhil S. Mande, Nithish Raja

Published Jul 6, 2026• 0 citations
arXivHTMLPDF

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.

DOI
10.48550/arxiv.2607.04850

Related papers

A General Composition Theorem for Approximate Degree

Samruddhi Pednekar, Supartha Podder

A longstanding open question in Boolean function complexity asks whether approximate degree composes multiplicatively under block composition. Although a general multiplicative upper bound is known, matching lower bounds have previously been established only for restricted classes of functions. We resolve this question for all total Boolean functions by proving the matching lower bound. Together with Sherstov's upper bound, our result shows that, for every pair of total Boolean functions $f:\{0,1\}^n\to\{0,1\}$ and $g:\{0,1\}^m\to\{0,1\}$, \[ \widetilde{deg}(f\circ g) = Θ\!\left( \widetilde{deg}(f)\,\widetilde{deg}(g) \right), \] where $\widetilde{deg}$ denotes constant-error approximate degree. We also consider the analogous question for exact quantum query complexity and give a counterexample showing that multiplicative composition fails in this setting.

cs.CCCross-listedarXiv:2609.30139•Sep 25, 2026•0 citations

On the Composition of Randomized Query Complexity and Approximate Degree

Sourav Chakraborty, Chandrima Kayal, Rajat Mittal +3 more

For any Boolean functions f and g, the question whether $$\text {R}(f\circ g) = \tilde{\Theta }(\text {R}(f) \cdot \text {R}(g))$$ is known as the composition question for the randomized query complexity. Similarly, the composition question for the approximate degree asks whether $$\widetilde{\text {deg}}(f\circ g) = \tilde{\Theta }(\widetilde{\text {deg}}(f)\cdot \widetilde{\text {deg}}(g))$$ . These questions are two of the most important and well-studied problems in the field of analysis of Boolean functions, and yet we are far from answering them satisfactorily. It is known that the measures compose if one assumes various properties of the outer function f (or inner function g). This paper extends the class of outer functions for which $$\text {R}$$ and $$\widetilde{\text {deg}}$$ compose. A recent landmark result (Ben-David and Blais, 2020) showed that $$\text {R}(f \circ g) = \Omega (\text {noisyR}(f)\cdot \text {R}(g))$$ . This implies that composition holds iff $$\text {noisyR}(f) = \tilde{\Theta }(\text {R}(f))$$ . We show two results: On the other hand, we prove that $$ \widetilde{\text {deg}}(f\circ g) = \widetilde{\Omega }(\sqrt{\text {bs}(f)} \cdot \widetilde{\text {deg}}(g)), $$ where $$\text {bs}(f)$$ is the block sensitivity of f. This implies that $$\widetilde{\text {deg}}$$ composes when $$\widetilde{\text {deg}}(f)$$ is asymptotically equal to $$\sqrt{\text {bs}(f)}$$ . It is already known that both $$\text {R}$$ and $$\widetilde{\text {deg}}$$ compose when the outer function is symmetric. We also extend these results to weaker notions of symmetry with respect to the outer function.

arXiv:2307.03900•Computational Complexity•Aug 20, 2026•0 citations

Restriction Trees for Sparsity and Applications

Arkadev Chattopadhyay, Yogesh Dahiya, Shachar Lovett

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: First, 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. Second, we consider more powerful representations using generalized monomials, where each monomial is an indicator of a sub-cube. There are 3n 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. Third, we show that for every total Boolean function f, the log of its De Morgan sparsity characterizes up to polynomial loss and ignoring poly-log(n) factors, the quantum and classical 2-party bounded-error communication complexity of f ∘ EQ4, where EQ4 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.

ACM Symposium on Theory of Computing (STOC)•Jun 9, 2026•0 citations

On the Probabilistic Degree of an nnn-variate Boolean Function

Srikanth Srinivasan, S. Venkitesh

Nisan and Szegedy (CC 1994) showed that any Boolean function $f:\{0,1\}^n\rightarrow \{0,1\}$ that depends on all its input variables, when represented as a real-valued multivariate polynomial $P(x_1,\ldots,x_n)$, has degree at least $\log n - O(\log \log n)$. This was improved to a tight $(\log n - O(1))$ bound by Chiarelli, Hatami and Saks (Combinatorica 2020). Similar statements are also known for other Boolean function complexity measures such as Sensitivity (Simon (FCT 1983)), Quantum query complexity, and Approximate degree (Ambainis and de Wolf (CC 2014)). In this paper, we address this question for \emph{Probabilistic degree}. The function $f$ has probabilistic degree at most $d$ if there is a random real-valued polynomial of degree at most $d$ that agrees with $f$ at each input with high probability. Our understanding of this complexity measure is significantly weaker than those above: for instance, we do not even know the probabilistic degree of the OR function, the best-known bounds put it between $(\log n)^{1/2-o(1)}$ and $O(\log n)$ (Beigel, Reingold, Spielman (STOC 1991); Tarui (TCS 1993); Harsha, Srinivasan (RSA 2019)). Here we can give a near-optimal understanding of the probabilistic degree of $n$-variate functions $f$, \emph{modulo} our lack of understanding of the probabilistic degree of OR. We show that if the probabilistic degree of OR is $(\log n)^c$, then the minimum possible probabilistic degree of such an $f$ is at least $(\log n)^{c/(c+1)-o(1)}$, and we show this is tight up to $(\log n)^{o(1)}$ factors.

arXiv:2107.03171•Leibniz international proceedings in informatics•Jan 1, 2021•0 citations

On the Approximate Non-Deterministic Degree of Total Boolean Functions

Samruddhi Pednekar, Supartha Podder

The approximate non-deterministic degree of a Boolean function $f$, denoted $\mathsf{ndeg}_ε(f)$ (written $\mathsf{N}_ε(f)$ for brevity), is the minimum degree of a real polynomial $p$ such that $0 \le |p(x)| \le ε$ whenever $f(x) = 0$, and $|p(x)| \ge 1$ whenever $f(x) = 1$. Unlike exact non-deterministic degree, which only requires the polynomial to be nonzero on $1$-inputs, this measure enforces a uniform gap: the polynomial must stay close to zero on all $0$-inputs and bounded away from zero on all $1$-inputs. The rational degree conjecture, open for over three decades, was recently resolved by Kothari, Kovacs-Deak, Wang, and Yang, who showed that for every total Boolean function $f$, \[ deg(f) \le \widetilde O\!\left(\operatorname{rdeg}(f)^3\right). \] In their paper, they explicitly propose a stronger conjecture: that approximate degree is polynomially bounded by $\mathsf{N}_ε(f)$ and $\mathsf{N}_ε(\overline{f})$ jointly, i.e., for every total Boolean function $f$ and every constant $0<ε<1$, \[ \widetilde{deg}(f) \le \operatorname{poly}(\mathsf N_ε(f), \mathsf N_ε(\overline f)). \] This conjecture, if true, would imply a polynomial version of the rational degree result and bring us closer to resolving de Wolf's longstanding non-deterministic degree conjecture. In this work, we make the first systematic progress on this problem, establishing the conjecture for several broad and natural function classes: monotone and unate functions, functions of bounded alternation number, symmetric functions, $k$-uniform hypergraph properties, and read-$k$ Disjunctive Normal Form (DNF) formulas.

cs.CCCross-listedarXiv:2605.23336•May 25, 2026•0 citations

Approximate Degree Composition for Recursive Functions

Sourav Chakraborty, Chandrima Kayal, Mittal, Rajat +2 more

Determining the approximate degree composition for Boolean functions remains a significant unsolved problem in Boolean function complexity. In recent decades, researchers have concentrated on proving that approximate degree composes for special types of inner and outer functions. An important and extensively studied class of functions are the recursive functions, i.e.~functions obtained by composing a base function with itself a number of times. Let $h^d$ denote the standard $d$-fold composition of the base function $h$. The main result of this work is to show that the approximate degree composes if either of the following conditions holds: (I) The outer function $f:\{0,1\}^n\to \{0,1\}$ is a recursive function of the form $h^d$, with $h$ being any base function and $d= Ω(\log\log n)$. (II) The inner function is a recursive function of the form $h^d$, with $h$ being any constant arity base function (other than AND and OR) and $d= Ω(\log\log n)$, where $n$ is the arity of the outer function. In terms of proof techniques, we first observe that the lower bound for composition can be obtained by introducing majority in between the inner and the outer functions. We then show that majority can be \emph{efficiently eliminated} if the inner or outer function is a recursive function.

arXiv:2407.08385•Leibniz international proceedings in informatics•Jan 1, 2024•0 citations
We introduce the subcube stifling number, a new combinatorial measure of total Boolean functions. This measure is the largest integer kkk such that, for every set SSS of at most kkk input variables and every assignment b∈{0,1}Sb \in \{0,1\}^Sb∈{0,1}S, there is a fixing of the variables outside SSS under which the resulting function on the free variables SSS is the point indicator I[xS=b]\mathbb{I}[x_S=b]I[xS​=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 fff has approximate degree O(μ(f))O(\sqrt{μ(f)})O(μ(f)​), then for every Boolean function ggg, 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(μ(f))O(\sqrt{μ(f)})O(μ(f)​). 2) We show that a random Boolean function on nnn input bits has subcube stifling number Θ(log⁡(n))Θ(\log(n))Θ(log(n)) with high probability. 3) We show that indicators of linear codes over F2\mathbb{F}_2F2​ 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(μ(f))O(\sqrt{μ(f)})O(μ(f)​); in fact, they have approximate degree Ω(μ(f))Ω(μ(f))Ω(μ(f)). The main question left open is whether there exists a Boolean function fff with approximate degree Θ(μ(f))Θ(\sqrt{μ(f)})Θ(μ(f)​). A positive answer would yield new instances of tight approximate-degree composition.
A longstanding open question in Boolean function complexity asks whether approximate degree composes multiplicatively under block composition. Although a general multiplicative upper bound is known, matching lower bounds have previously been established only for restricted classes of functions. We resolve this question for all total Boolean functions by proving the matching lower bound. Together with Sherstov's upper bound, our result shows that, for every pair of total Boolean functions f:{0,1}n→{0,1}f:\{0,1\}^n\to\{0,1\}f:{0,1}n→{0,1} and g:{0,1}m→{0,1}g:\{0,1\}^m\to\{0,1\}g:{0,1}m→{0,1}, deg~(f∘g)=Θ ⁣(deg~(f) deg~(g)), \widetilde{deg}(f\circ g) = Θ\!\left( \widetilde{deg}(f)\,\widetilde{deg}(g) \right), deg​(f∘g)=Θ(deg​(f)deg​(g)), where deg~\widetilde{deg}deg​ denotes constant-error approximate degree. We also consider the analogous question for exact quantum query complexity and give a counterexample showing that multiplicative composition fails in this setting.
For any Boolean functions f and g, the question whether R(f∘g)=Θ~(R(f)⋅R(g))\text {R}(f\circ g) = \tilde{\Theta }(\text {R}(f) \cdot \text {R}(g))R(f∘g)=Θ~(R(f)⋅R(g)) is known as the composition question for the randomized query complexity. Similarly, the composition question for the approximate degree asks whether deg~(f∘g)=Θ~(deg~(f)⋅deg~(g))\widetilde{\text {deg}}(f\circ g) = \tilde{\Theta }(\widetilde{\text {deg}}(f)\cdot \widetilde{\text {deg}}(g))deg​(f∘g)=Θ~(deg​(f)⋅deg​(g)) . These questions are two of the most important and well-studied problems in the field of analysis of Boolean functions, and yet we are far from answering them satisfactorily. It is known that the measures compose if one assumes various properties of the outer function f (or inner function g). This paper extends the class of outer functions for which R\text {R}R and deg~\widetilde{\text {deg}}deg​ compose. A recent landmark result (Ben-David and Blais, 2020) showed that R(f∘g)=Ω(noisyR(f)⋅R(g))\text {R}(f \circ g) = \Omega (\text {noisyR}(f)\cdot \text {R}(g))R(f∘g)=Ω(noisyR(f)⋅R(g)) . This implies that composition holds iff noisyR(f)=Θ~(R(f))\text {noisyR}(f) = \tilde{\Theta }(\text {R}(f))noisyR(f)=Θ~(R(f)) . We show two results: On the other hand, we prove that deg~(f∘g)=Ω~(bs(f)⋅deg~(g)), \widetilde{\text {deg}}(f\circ g) = \widetilde{\Omega }(\sqrt{\text {bs}(f)} \cdot \widetilde{\text {deg}}(g)), deg​(f∘g)=Ω(bs(f)​⋅deg​(g)), where bs(f)\text {bs}(f)bs(f) is the block sensitivity of f. This implies that deg~\widetilde{\text {deg}}deg​ composes when deg~(f)\widetilde{\text {deg}}(f)deg​(f) is asymptotically equal to bs(f)\sqrt{\text {bs}(f)}bs(f)​ . It is already known that both R\text {R}R and deg~\widetilde{\text {deg}}deg​ compose when the outer function is symmetric. We also extend these results to weaker notions of symmetry with respect to the outer function.
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: First, 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. Second, we consider more powerful representations using generalized monomials, where each monomial is an indicator of a sub-cube. There are 3n 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. Third, we show that for every total Boolean function f, the log of its De Morgan sparsity characterizes up to polynomial loss and ignoring poly-log(n) factors, the quantum and classical 2-party bounded-error communication complexity of f ∘ EQ4, where EQ4 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.
Nisan and Szegedy (CC 1994) showed that any Boolean function f:{0,1}n→{0,1}f:\{0,1\}^n\rightarrow \{0,1\}f:{0,1}n→{0,1} that depends on all its input variables, when represented as a real-valued multivariate polynomial P(x1,…,xn)P(x_1,\ldots,x_n)P(x1​,…,xn​), has degree at least log⁡n−O(log⁡log⁡n)\log n - O(\log \log n)logn−O(loglogn). This was improved to a tight (log⁡n−O(1))(\log n - O(1))(logn−O(1)) bound by Chiarelli, Hatami and Saks (Combinatorica 2020). Similar statements are also known for other Boolean function complexity measures such as Sensitivity (Simon (FCT 1983)), Quantum query complexity, and Approximate degree (Ambainis and de Wolf (CC 2014)). In this paper, we address this question for \emph{Probabilistic degree}. The function fff has probabilistic degree at most ddd if there is a random real-valued polynomial of degree at most ddd that agrees with fff at each input with high probability. Our understanding of this complexity measure is significantly weaker than those above: for instance, we do not even know the probabilistic degree of the OR function, the best-known bounds put it between (log⁡n)1/2−o(1)(\log n)^{1/2-o(1)}(logn)1/2−o(1) and O(log⁡n)O(\log n)O(logn) (Beigel, Reingold, Spielman (STOC 1991); Tarui (TCS 1993); Harsha, Srinivasan (RSA 2019)). Here we can give a near-optimal understanding of the probabilistic degree of nnn-variate functions fff, \emph{modulo} our lack of understanding of the probabilistic degree of OR. We show that if the probabilistic degree of OR is (log⁡n)c(\log n)^c(logn)c, then the minimum possible probabilistic degree of such an fff is at least (log⁡n)c/(c+1)−o(1)(\log n)^{c/(c+1)-o(1)}(logn)c/(c+1)−o(1), and we show this is tight up to (log⁡n)o(1)(\log n)^{o(1)}(logn)o(1) factors.
The approximate non-deterministic degree of a Boolean function fff, denoted ndegε(f)\mathsf{ndeg}_ε(f)ndegε​(f) (written Nε(f)\mathsf{N}_ε(f)Nε​(f) for brevity), is the minimum degree of a real polynomial ppp such that 0≤∣p(x)∣≤ε0 \le |p(x)| \le ε0≤∣p(x)∣≤ε whenever f(x)=0f(x) = 0f(x)=0, and ∣p(x)∣≥1|p(x)| \ge 1∣p(x)∣≥1 whenever f(x)=1f(x) = 1f(x)=1. Unlike exact non-deterministic degree, which only requires the polynomial to be nonzero on 111-inputs, this measure enforces a uniform gap: the polynomial must stay close to zero on all 000-inputs and bounded away from zero on all 111-inputs. The rational degree conjecture, open for over three decades, was recently resolved by Kothari, Kovacs-Deak, Wang, and Yang, who showed that for every total Boolean function fff, deg(f)≤O~ ⁣(rdeg⁡(f)3). deg(f) \le \widetilde O\!\left(\operatorname{rdeg}(f)^3\right). deg(f)≤O(rdeg(f)3). In their paper, they explicitly propose a stronger conjecture: that approximate degree is polynomially bounded by Nε(f)\mathsf{N}_ε(f)Nε​(f) and Nε(f‾)\mathsf{N}_ε(\overline{f})Nε​(f​) jointly, i.e., for every total Boolean function fff and every constant 0<ε<10<ε<10<ε<1, deg~(f)≤poly⁡(Nε(f),Nε(f‾)). \widetilde{deg}(f) \le \operatorname{poly}(\mathsf N_ε(f), \mathsf N_ε(\overline f)). deg​(f)≤poly(Nε​(f),Nε​(f​)). This conjecture, if true, would imply a polynomial version of the rational degree result and bring us closer to resolving de Wolf's longstanding non-deterministic degree conjecture. In this work, we make the first systematic progress on this problem, establishing the conjecture for several broad and natural function classes: monotone and unate functions, functions of bounded alternation number, symmetric functions, kkk-uniform hypergraph properties, and read-kkk Disjunctive Normal Form (DNF) formulas.
Determining the approximate degree composition for Boolean functions remains a significant unsolved problem in Boolean function complexity. In recent decades, researchers have concentrated on proving that approximate degree composes for special types of inner and outer functions. An important and extensively studied class of functions are the recursive functions, i.e.~functions obtained by composing a base function with itself a number of times. Let hdh^dhd denote the standard ddd-fold composition of the base function hhh. The main result of this work is to show that the approximate degree composes if either of the following conditions holds: (I) The outer function f:{0,1}n→{0,1}f:\{0,1\}^n\to \{0,1\}f:{0,1}n→{0,1} is a recursive function of the form hdh^dhd, with hhh being any base function and d=Ω(log⁡log⁡n)d= Ω(\log\log n)d=Ω(loglogn). (II) The inner function is a recursive function of the form hdh^dhd, with hhh being any constant arity base function (other than AND and OR) and d=Ω(log⁡log⁡n)d= Ω(\log\log n)d=Ω(loglogn), where nnn is the arity of the outer function. In terms of proof techniques, we first observe that the lower bound for composition can be obtained by introducing majority in between the inner and the outer functions. We then show that majority can be \emph{efficiently eliminated} if the inner or outer function is a recursive function.