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.
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.
Nisan and Szegedy (CC 1994) showed that any Boolean function f : {0, 1}n → {0, 1} that depends on all its input variables, when represented as a real-valued multivariate polynomial P(x1,..., xn), 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 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, 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.
Nisan and Szegedy (CC 1994) showed that any Boolean function f:{0,1}n→{0,1} that depends on all its input variables, when represented as a real-valued multivariate polynomial P(x1,…,xn), has degree at least logn−O(loglogn). This was improved to a tight (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 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 (logn)1/2−o(1) and 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 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 (logn)c, then the minimum possible probabilistic degree of such an f is at least (logn)c/(c+1)−o(1), and we show this is tight up to (logn)o(1) factors.
The approximate non-deterministic degree of a Boolean function f, denoted ndegε(f) (written Nε(f) for brevity), is the minimum degree of a real polynomial p such that 0≤∣p(x)∣≤ε whenever f(x)=0, and ∣p(x)∣≥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)≤O(rdeg(f)3).
In their paper, they explicitly propose a stronger conjecture: that approximate degree is polynomially bounded by Nε(f) and Nε(f) jointly, i.e., for every total Boolean function f and every constant 0<ε<1, 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, k-uniform hypergraph properties, and read-k Disjunctive Normal Form (DNF) formulas.
The approximate degree of a Boolean function f(x1,x2,…,xn) is the minimum degree of a real polynomial that approximates f pointwise within 1/3. Upper bounds on approximate degree have a variety of applications in learning theory, differential privacy, and algorithm design in general. Nearly all known upper bounds on approximate degree arise in an existential manner from bounds on quantum query complexity. We develop a first-principles, classical approach to the polynomial approximation of Boolean functions. We use it to give the first constructive upper bounds on the approximate degree of several fundamental problems: - O(n43−4(2k−1)1) for the k-element distinctness problem; - O(n1−k+11) for the k-subset sum problem; - O(n1−k+11) for any k-DNF or k-CNF formula; - O(n3/4) for the surjectivity problem. In all cases, we obtain explicit, closed-form approximating polynomials that are unrelated to the quantum arguments from previous work. Our first three results match the bounds from quantum query complexity. Our fourth result improves polynomially on the Θ(n) quantum query complexity of the problem and refutes the conjecture by several experts that surjectivity has approximate degree Ω(n). In particular, we exhibit the first natural problem with a polynomial gap between approximate degree and quantum query complexity.
The approximate degree of a Boolean function f(x1,x2,…,xn) is the minimum degree of a real polynomial that approximates f pointwise within 1/3. Upper bounds on approximate degree have a variety of applications in learning theory, differential privacy, and algorithm design in general. Nearly all known upper bounds on approximate degree arise in an existential manner from bounds on quantum query complexity. We develop a novel, first-principles approach to the polynomial approximation of Boolean functions. We use it to give the first constructive upper bounds on the approximate degree of several fundamental problems: O(n43−4(2k−1)1) for the k-element distinctness problem; O(n1−k+11) for the k-subset sum problem; O(n1−k+11) for any k-DNF or k-CNF formula; and O(n3/4) for the surjectivity problem. In all cases, we obtain explicit, closed-form approximating polynomials that are unrelated to the quantum arguments from previous work. Our first three results match the bounds from quantum query complexity. Our fourth result improves polynomially on the Θ(n) quantum query complexity of the problem and refutes the conjecture by several experts that surjectivity has approximate degree Ω(n). In particular, we exhibit the first natural problem with a polynomial gap between approximate degree and quantum query complexity.
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.