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:2410.19949

Jackson's inequality on the hypercube

Paata Ivanisvili, Roman Vershynin, Xiaoju Xie

Published Oct 25, 2024• 0 citations
arXivHTMLPDF

Abstract

We investigate the best constant $J(n,d)$ such that Jackson's inequality \[ \inf_{\mathrm{deg}(g) \leq d} \|f - g\|_{\infty} \leq J(n,d) \, s(f), \] holds for all functions $f$ on the hypercube $\{0,1\}^n$, where $s(f)$ denotes the sensitivity of $f$. We show that the quantity $J(n, 0.499n)$ is bounded below by an absolute positive constant, independent of $n$. This complements Wagner's theorem, which establishes that $J(n,d)\leq 1 $. As a first application we show that reverse Bernstein inequality fails in the tail space $L^{1}_{\geq 0.499n}$ improving over previously known counterexamples in $L^{1}_{\geq C \log \log (n)}$. As a second application, we show that there exists a function $f : \{0,1\}^n \to [-1,1]$ whose sensitivity $s(f)$ remains constant, independent of $n$, while the approximate degree grows linearly with $n$. This result implies that the sensitivity theorem $s(f) \geq Ω(\mathrm{deg}(f)^C)$ fails in the strongest sense for bounded real-valued functions even when $\mathrm{deg}(f)$ is relaxed to the approximate degree. We also show that in the regime $d = (1 - δ)n$, the bound \[ J(n,d) \leq C \min\{δ, \max\{δ^2, n^{-2/3}\}\} \] holds. Moreover, when restricted to symmetric real-valued functions, we obtain $J_{\mathrm{symmetric}}(n,d) \leq C/d$ and the decay $1/d$ is sharp. Finally, we present results for a subspace approximation problem: we show that there exists a subspace $E$ of dimension $2^{n-1}$ such that $\inf_{g \in E} \|f - g\|_{\infty} \leq s(f)/n$ holds for all $f$.

DOI
10.48550/arxiv.2410.19949

Related papers

Comparing the Sensitivity and Degree of Boolean Functions via the Hypercube

Anne-Caroline Rupp

This thesis studies three complexity measures of total Boolean functions f:{0,1}n → {0,1}: maximum sensitivity s(f), polynomial degree deg(f), and spectral sensitivity λ(f), where λ(f) is defined as the spectral norm of the adjacency matrix of the sensitivity graph. Building on the results of Aaronson et al., we examine the inequality chain √s(f) ≤ λ(f) ≤ deg(f) and investigate whether all three quantities can be simultaneously equal. The first part of the thesis reverse engineers the equality cases of the two known inequalities to isolate necessary extremal conditions on both the Fourier structure of f and the local geometry of its sensitivity graph. The second part develops Python-based exhaustive and constrained searches to test the first nontrivial candidate profiles. We compute full distributions of s(f), deg(f), and λ(f) for all Boolean functions on n=3 and n=4, showing in particular that no function realizes the candidate (s(f), λ(f), deg(f)) = (4,2,2) at n=4. We then use Möbius-based and CSP-based enumeration to study all real-degree-≤2 Boolean functions through higher dimensions, obtaining repeated evidence that s(f) ≤ 3 in this family and thereby excluding the (4,2,2) case in the tested range. Together, the theoretical and computational results support the view that the simultaneous tightness of √s(f) = λ(f) = deg(f) is obstructed by strong structural incompatibilities beyond the trivial degree-1 case.

•Jun 1, 2026•0 citations

Degree and Sensitivity: tails of two distributions

Parikshit Gopalan, Rocco A. Servedio, Avishay Tal +1 more

The sensitivity of a Boolean function f is the maximum over all inputs x, of the number of sensitive coordinates of x. The well-known sensitivity conjecture of Nisan (see also Nisan and Szegedy) states that every sensitivity-s Boolean function can be computed by a polynomial over the reals of degree poly(s). The best known upper bounds on degree, however, are exponential rather than polynomial in s. Our main result is an approximate version of the conjecture: every Boolean function with sensitivity s can be epsilon-approximated (in L_2) by a polynomial whose degree is O(s log(1/epsilon)). This is the first improvement on the folklore bound of s/epsilon. Further, we show that improving the bound to O(s^c log(1/epsilon)^d)$ for any d < 1 and any c > 0 will imply the sensitivity conjecture. Thus our result is essentially the best one can hope for without proving the conjecture. We postulate a robust analogue of the sensitivity conjecture: if most inputs to a Boolean function f have low sensitivity, then most of the Fourier mass of f is concentrated on small subsets, and present an approach towards proving this conjecture.

arXiv:1604.07432•Electronic colloquium on computational complexity•Apr 25, 2016•8 citations

The Large-Error Approximate Degree of AC^0

Mark Bun, Justin Thaler

We prove two new results about the inability of low-degree polynomials to uniformly approximate constant-depth circuits, even to slightly-better-than-trivial error. First, we prove a tight Omega~(n^{1/2}) lower bound on the threshold degree of the SURJECTIVITY function on n variables. This matches the best known threshold degree bound for any AC^0 function, previously exhibited by a much more complicated circuit of larger depth (Sherstov, FOCS 2015). Our result also extends to a 2^{Omega~(n^{1/2})} lower bound on the sign-rank of an AC^0 function, improving on the previous best bound of 2^{Omega(n^{2/5})} (Bun and Thaler, ICALP 2016). Second, for any delta>0, we exhibit a function f : {-1,1}^n -> {-1,1} that is computed by a circuit of depth O(1/delta) and is hard to approximate by polynomials in the following sense: f cannot be uniformly approximated to error epsilon=1-2^{-Omega(n^{1-delta})}, even by polynomials of degree n^{1-delta}. Our recent prior work (Bun and Thaler, FOCS 2017) proved a similar lower bound, but which held only for error epsilon=1/3. Our result implies 2^{Omega(n^{1-delta})} lower bounds on the complexity of AC^0 under a variety of basic measures such as discrepancy, margin complexity, and threshold weight. This nearly matches the trivial upper bound of 2^{O(n)} that holds for every function. The previous best lower bound on AC^0 for these measures was 2^{Omega(n^{1/2})} (Sherstov, FOCS 2015). Additional applications in learning theory, communication complexity, and cryptography are described.

Leibniz international proceedings in informatics•Jan 1, 2019•0 citations

The Approximate Degree of Bipartite Perfect Matching

Gal Beniamini

The approximate degree of a Boolean function is the least degree of a real multilinear polynomial approximating it in the $\ell_\infty$-norm over the Boolean hypercube. We show that the approximate degree of the Bipartite Perfect Matching function, which is the indicator over all bipartite graphs having a perfect matching, is $\widetildeΘ(n^{3/2})$. The upper bound is obtained by fully characterizing the unique multilinear polynomial representing the Boolean dual of the perfect matching function, over the reals. Crucially, we show that this polynomial has very small $\ell_1$-norm -- only exponential in $Θ(n \log n)$. The lower bound follows by bounding the spectral sensitivity of the perfect matching function, which is the spectral radius of its cut-graph on the hypercube \cite{aaronson2020degree, huang2019induced}. We show that the spectral sensitivity of perfect matching is exactly $Θ(n^{3/2})$.

arXiv:2004.14318•Leibniz international proceedings in informatics•Apr 29, 2020•2 citations

Dual Lower Bounds for Approximate Degree and Markov-Bernstein Inequalities

Mark Bun, Justin Thaler

The $ε$-approximate degree of a Boolean function $f: \{-1, 1\}^n \to \{-1, 1\}$ is the minimum degree of a real polynomial that approximates $f$ to within $ε$ in the $\ell_\infty$ norm. We prove several lower bounds on this important complexity measure by explicitly constructing solutions to the dual of an appropriate linear program. Our first result resolves the $ε$-approximate degree of the two-level AND-OR tree for any constant $ε> 0$. We show that this quantity is $Θ(\sqrt{n})$, closing a line of incrementally larger lower bounds. The same lower bound was recently obtained independently by Sherstov using related techniques. Our second result gives an explicit dual polynomial that witnesses a tight lower bound for the approximate degree of any symmetric Boolean function, addressing a question of Špalek. Our final contribution is to reprove several Markov-type inequalities from approximation theory by constructing explicit dual solutions to natural linear programs. These inequalities underly the proofs of many of the best-known approximate degree lower bounds, and have important uses throughout theoretical computer science.

arXiv:1302.6191•Feb 25, 2013•1 citation

Approximate Degree, Weight, and Indistinguishability

Xuangui Huang, Emanuele Viola

We prove that the OR function on {-1,1\} n can be pointwise approximated with error ε by a polynomial of degree O ( k ) and weight 2 O ( n log (1/ε)/k) , for any k ≥ √ n log (1/ε). This result is tight for any k ≤ (1-Ω (1)) n . Previous results were either not tight or had ε = Ω (1). In general, we obtain a tight approximate degree-weight result for any symmetric function. Building on this, we also obtain an approximate degree-weight result for bounded-width CNF. For these two classes no such result was known. We prove that the \( \mathsf {OR} \) function on \( \lbrace -1,1\rbrace ^n \) can be pointwise approximated with error \( \epsilon \) by a polynomial of degree \( O(k) \) and weight \( 2^{O(n \log (1/\epsilon) /k)} \) , for any \( k \ge \sqrt {n \log (1/\epsilon)} \) . This result is tight for any \( k \le (1-\Omega (1))n \) . Previous results were either not tight or had \( \epsilon = \Omega (1) \) . In general, we obtain a tight approximate degree-weight result for any symmetric function. Building on this, we also obtain an approximate degree-weight result for bounded-width \( \mathsf {CNF} \) . For these two classes no such result was known. One motivation for such results comes from the study of indistinguishability. Two distributions \( P \) , \( Q \) over \( n \) -bit strings are \( (k,\delta) \) -indistinguishable if their projections on any \( k \) bits have statistical distance at most \( \delta \) . The above approximations give values of \( (k,\delta) \) that suffice to fool \( \mathsf {OR} \) , symmetric functions, and bounded-width \( \mathsf {CNF} \) , and the first result is tight for all \( k \) while the second result is tight for \( k \le (1-\Omega (1))n \) . We also show that any two \( (k, \delta) \) -indistinguishable distributions are \( O(n^{k/2}\delta) \) -close to two distributions that are \( (k,0) \) -indistinguishable, improving the previous bound of \( O(n)^k \delta \) . Finally, we present proofs of some known approximate degree lower bounds in the language of indistinguishability, which we find more intuitive.

ACM Transactions on Computation Theory•Mar 4, 2022•3 citations
We investigate the best constant J(n,d)J(n,d)J(n,d) such that Jackson's inequality [ \inf_{\mathrm{deg}(g) \leq d} |f - g|_{\infty} \leq J(n,d) , s(f), ] holds for all functions fff on the hypercube {0,1}n\{0,1\}^n{0,1}n, where s(f)s(f)s(f) denotes the sensitivity of fff. We show that the quantity J(n,0.499n)J(n, 0.499n)J(n,0.499n) is bounded below by an absolute positive constant, independent of nnn. This complements Wagner's theorem, which establishes that J(n,d)≤1J(n,d)\leq 1 J(n,d)≤1. As a first application we show that reverse Bernstein inequality fails in the tail space L≥0.499n1L^{1}_{\geq 0.499n}L≥0.499n1​ improving over previously known counterexamples in L≥Clog⁡log⁡(n)1L^{1}_{\geq C \log \log (n)}L≥Cloglog(n)1​. As a second application, we show that there exists a function f:{0,1}n→[−1,1]f : \{0,1\}^n \to [-1,1]f:{0,1}n→[−1,1] whose sensitivity s(f)s(f)s(f) remains constant, independent of nnn, while the approximate degree grows linearly with nnn. This result implies that the sensitivity theorem s(f)≥Ω(deg(f)C)s(f) \geq Ω(\mathrm{deg}(f)^C)s(f)≥Ω(deg(f)C) fails in the strongest sense for bounded real-valued functions even when deg(f)\mathrm{deg}(f)deg(f) is relaxed to the approximate degree. We also show that in the regime d=(1−δ)nd = (1 - δ)nd=(1−δ)n, the bound [ J(n,d) \leq C \min{δ, \max{δ^2, n^{-2/3}}} ] holds. Moreover, when restricted to symmetric real-valued functions, we obtain Jsymmetric(n,d)≤C/dJ_{\mathrm{symmetric}}(n,d) \leq C/dJsymmetric​(n,d)≤C/d and the decay 1/d1/d1/d is sharp. Finally, we present results for a subspace approximation problem: we show that there exists a subspace EEE of dimension 2n−12^{n-1}2n−1 such that inf⁡g∈E∥f−g∥∞≤s(f)/n\inf_{g \in E} \|f - g\|_{\infty} \leq s(f)/ninfg∈E​∥f−g∥∞​≤s(f)/n holds for all fff.
This thesis studies three complexity measures of total Boolean functions f:{0,1}n → {0,1}: maximum sensitivity s(f), polynomial degree deg(f), and spectral sensitivity λ(f), where λ(f) is defined as the spectral norm of the adjacency matrix of the sensitivity graph. Building on the results of Aaronson et al., we examine the inequality chain √s(f) ≤ λ(f) ≤ deg(f) and investigate whether all three quantities can be simultaneously equal. The first part of the thesis reverse engineers the equality cases of the two known inequalities to isolate necessary extremal conditions on both the Fourier structure of f and the local geometry of its sensitivity graph. The second part develops Python-based exhaustive and constrained searches to test the first nontrivial candidate profiles. We compute full distributions of s(f), deg(f), and λ(f) for all Boolean functions on n=3 and n=4, showing in particular that no function realizes the candidate (s(f), λ(f), deg(f)) = (4,2,2) at n=4. We then use Möbius-based and CSP-based enumeration to study all real-degree-≤2 Boolean functions through higher dimensions, obtaining repeated evidence that s(f) ≤ 3 in this family and thereby excluding the (4,2,2) case in the tested range. Together, the theoretical and computational results support the view that the simultaneous tightness of √s(f) = λ(f) = deg(f) is obstructed by strong structural incompatibilities beyond the trivial degree-1 case.
The sensitivity of a Boolean function f is the maximum over all inputs x, of the number of sensitive coordinates of x. The well-known sensitivity conjecture of Nisan (see also Nisan and Szegedy) states that every sensitivity-s Boolean function can be computed by a polynomial over the reals of degree poly(s). The best known upper bounds on degree, however, are exponential rather than polynomial in s. Our main result is an approximate version of the conjecture: every Boolean function with sensitivity s can be epsilon-approximated (in L_2) by a polynomial whose degree is O(s log(1/epsilon)). This is the first improvement on the folklore bound of s/epsilon. Further, we show that improving the bound to O(s^c log(1/epsilon)^d)$ for any d < 1 and any c > 0 will imply the sensitivity conjecture. Thus our result is essentially the best one can hope for without proving the conjecture. We postulate a robust analogue of the sensitivity conjecture: if most inputs to a Boolean function f have low sensitivity, then most of the Fourier mass of f is concentrated on small subsets, and present an approach towards proving this conjecture.
We prove two new results about the inability of low-degree polynomials to uniformly approximate constant-depth circuits, even to slightly-better-than-trivial error. First, we prove a tight Omega~(n^{1/2}) lower bound on the threshold degree of the SURJECTIVITY function on n variables. This matches the best known threshold degree bound for any AC^0 function, previously exhibited by a much more complicated circuit of larger depth (Sherstov, FOCS 2015). Our result also extends to a 2^{Omega~(n^{1/2})} lower bound on the sign-rank of an AC^0 function, improving on the previous best bound of 2^{Omega(n^{2/5})} (Bun and Thaler, ICALP 2016). Second, for any delta>0, we exhibit a function f : {-1,1}^n -> {-1,1} that is computed by a circuit of depth O(1/delta) and is hard to approximate by polynomials in the following sense: f cannot be uniformly approximated to error epsilon=1-2^{-Omega(n^{1-delta})}, even by polynomials of degree n^{1-delta}. Our recent prior work (Bun and Thaler, FOCS 2017) proved a similar lower bound, but which held only for error epsilon=1/3. Our result implies 2^{Omega(n^{1-delta})} lower bounds on the complexity of AC^0 under a variety of basic measures such as discrepancy, margin complexity, and threshold weight. This nearly matches the trivial upper bound of 2^{O(n)} that holds for every function. The previous best lower bound on AC^0 for these measures was 2^{Omega(n^{1/2})} (Sherstov, FOCS 2015). Additional applications in learning theory, communication complexity, and cryptography are described.
The approximate degree of a Boolean function is the least degree of a real multilinear polynomial approximating it in the ℓ∞\ell_\inftyℓ∞​-norm over the Boolean hypercube. We show that the approximate degree of the Bipartite Perfect Matching function, which is the indicator over all bipartite graphs having a perfect matching, is Θ~(n3/2)\widetildeΘ(n^{3/2})Θ(n3/2). The upper bound is obtained by fully characterizing the unique multilinear polynomial representing the Boolean dual of the perfect matching function, over the reals. Crucially, we show that this polynomial has very small ℓ1\ell_1ℓ1​-norm -- only exponential in Θ(nlog⁡n)Θ(n \log n)Θ(nlogn). The lower bound follows by bounding the spectral sensitivity of the perfect matching function, which is the spectral radius of its cut-graph on the hypercube \cite{aaronson2020degree, huang2019induced}. We show that the spectral sensitivity of perfect matching is exactly Θ(n3/2)Θ(n^{3/2})Θ(n3/2).
The εεε-approximate degree of a Boolean function f:{−1,1}n→{−1,1}f: \{-1, 1\}^n \to \{-1, 1\}f:{−1,1}n→{−1,1} is the minimum degree of a real polynomial that approximates fff to within εεε in the ℓ∞\ell_\inftyℓ∞​ norm. We prove several lower bounds on this important complexity measure by explicitly constructing solutions to the dual of an appropriate linear program. Our first result resolves the εεε-approximate degree of the two-level AND-OR tree for any constant ε>0ε> 0ε>0. We show that this quantity is Θ(n)Θ(\sqrt{n})Θ(n​), closing a line of incrementally larger lower bounds. The same lower bound was recently obtained independently by Sherstov using related techniques. Our second result gives an explicit dual polynomial that witnesses a tight lower bound for the approximate degree of any symmetric Boolean function, addressing a question of Špalek. Our final contribution is to reprove several Markov-type inequalities from approximation theory by constructing explicit dual solutions to natural linear programs. These inequalities underly the proofs of many of the best-known approximate degree lower bounds, and have important uses throughout theoretical computer science.
We prove that the OR function on {-1,1\} n can be pointwise approximated with error ε by a polynomial of degree O ( k ) and weight 2 O ( n log (1/ε)/k) , for any k ≥ √ n log (1/ε). This result is tight for any k ≤ (1-Ω (1)) n . Previous results were either not tight or had ε = Ω (1). In general, we obtain a tight approximate degree-weight result for any symmetric function. Building on this, we also obtain an approximate degree-weight result for bounded-width CNF. For these two classes no such result was known. We prove that the OR \mathsf {OR} OR function on {−1,1}n \lbrace -1,1\rbrace ^n {−1,1}n can be pointwise approximated with error ϵ \epsilon ϵ by a polynomial of degree O(k) O(k) O(k) and weight 2O(nlog⁡(1/ϵ)/k) 2^{O(n \log (1/\epsilon) /k)} 2O(nlog(1/ϵ)/k) , for any k≥nlog⁡(1/ϵ) k \ge \sqrt {n \log (1/\epsilon)} k≥nlog(1/ϵ)​ . This result is tight for any k≤(1−Ω(1))n k \le (1-\Omega (1))n k≤(1−Ω(1))n . Previous results were either not tight or had ϵ=Ω(1) \epsilon = \Omega (1) ϵ=Ω(1) . In general, we obtain a tight approximate degree-weight result for any symmetric function. Building on this, we also obtain an approximate degree-weight result for bounded-width CNF \mathsf {CNF} CNF . For these two classes no such result was known. One motivation for such results comes from the study of indistinguishability. Two distributions P P P , Q Q Q over n n n -bit strings are (k,δ) (k,\delta) (k,δ) -indistinguishable if their projections on any k k k bits have statistical distance at most δ \delta δ . The above approximations give values of (k,δ) (k,\delta) (k,δ) that suffice to fool OR \mathsf {OR} OR , symmetric functions, and bounded-width CNF \mathsf {CNF} CNF , and the first result is tight for all k k k while the second result is tight for k≤(1−Ω(1))n k \le (1-\Omega (1))n k≤(1−Ω(1))n . We also show that any two (k,δ) (k, \delta) (k,δ) -indistinguishable distributions are O(nk/2δ) O(n^{k/2}\delta) O(nk/2δ) -close to two distributions that are (k,0) (k,0) (k,0) -indistinguishable, improving the previous bound of O(n)kδ O(n)^k \delta O(n)kδ . Finally, we present proofs of some known approximate degree lower bounds in the language of indistinguishability, which we find more intuitive.