The approximate degree of a Boolean function f : {-1, 1}n→ {-1, 1} is the least degree of a real polynomial that approximates f pointwise to error at most 1/3. We introduce a generic method for increasing the approximate degree of a given function, while preserving its computability by constant-depth circuits. Specifically, we show how to transform any Boolean function f with approximate degree d into a function F on O(n · polylog(n)) variables with approximate degree at least D = Ω(n1/3· d2/3). In particular, if d = n1-Ω(1), then D is polynomially larger than d. Moreover, if f is computed by a constant-depth polynomial-size Boolean circuit, then so is F. By recursively applying our transformation, for any constant δ > 0 we exhibit an AC0function of approximate degree Ω(n1-δ). This improves over the best previous lower bound of Ω(n2/3) due to Aaronson and Shi (J. ACM 2004), and nearly matches the trivial upper bound of n that holds for any function. Our lower bounds also apply to (quasipolynomial-size) DNFs of polylogarithmic width. We describe several applications of these results. We give: · For any constant δ > 0, an Ω(n1-δ) lower bound on the quantum communication complexity of a function in AC0. · A Boolean function f with approximate degree at least C(f)2-o(1), where C(f) is the certificate complexity of f. This separation is optimal up to the o(1) term in the exponent. · Improved secret sharing schemes with reconstruction procedures in AC0.
The degree of a polynomial representing (or approximating) a function f is a lower bound for the quantum query complexity of f. This observation has been a source of many lower bounds on quantum algorithms. It has been an open problem whether this lower bound is tight. This is why Boolean functions are needed with a high number of essential variables and a low polynomial degree. Unfortunately, it is a well-known problem to construct such functions. The best separation between these two complexity measures of a Boolean function was exhibited by Ambai- nis [5]. He constructed functions with polynomial degree M and number of variables Omega(M2). We improve such a separation to become exponential. On the other hand, we use a computerized exhaustive search to prove tightness of this bound.
The approximate degree of a Boolean function
f:{−1,1}n→{−1,1} is the least degree of a real polynomial that approximates
f pointwise to error at most 1/3. We introduce a generic method for increasing the approximate degree of a given function, while preserving its computability by constant-depth circuits. Specifically, we show how to transform any Boolean function
f with approximate degree
d into a function
F on
O(n⋅polylog(n)) variables with approximate degree at least
D=Ω(n1/3⋅d2/3). In particular, if
d=n1−Ω(1), then
D is polynomially larger than
d. Moreover, if
f is computed by a polynomial-size Boolean circuit of constant depth, then so is
F. By recursively applying our transformation, for any constant
δ>0 we exhibit an AC
0 function of approximate degree
Ω(n1−δ). This improves upon the best previous lower bound of
Ω(n2/3) due to Aaronson and Shi [ J. ACM, 51 (2004), pp. 595--605] and nearly matches the trivial upper bound of
n that holds for any function. Our lower bounds also apply to (quasipolynomial-size) disjunctive normal forms of polylogarithmic width. We describe several applications of these results and provide the following: (i) for any constant
δ>0, an
Ω(n1−δ) lower bound on the quantum communication complexity of a function in AC
0; (ii) a Boolean function
f with approximate degree at least
C(f)2−o(1), where
C(f) is the certificate complexity of
f; this separation is optimal up to the
o(1) term in the exponent; (iii) improved secret sharing schemes with reconstruction procedures in AC
0.
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.
We prove a simple, nearly tight lower bound on the approximate degree of the two-level AND-OR tree using symmetrization arguments. Specifically, we show that ˜ deg(AND m ˆ OR n ) = ˜ Ω(√ mn ). We prove this lower bound via reduction to the OR function through a series of symmetrization steps, in contrast to most other proofs that involve formulating approximate degree as a linear program [6, 10, 21]. Our proof also demonstrates the power of a symmetrization technique involving Laurent polynomials (polynomials with negative exponents) that was previously introduced by Aaronson et al. [2].