ABSTRACT. The approximate degree of a Boolean function f is the least degree of a real polynomial that approximates f within 1=3 at every point. We prove that the functionVn iD1 Wn jD1 xij, known as the AND-OR tree, has approximate degree˝.n/: This lower bound is tight and closes a line of research on the problem, the best previous bound being ˝.n0:75/. More generally, we prove that the function
ABSTRACT. The approximate degree of a Boolean function f is the least degree of a real polynomial that approximates f within 1=3 at every point. We prove that the functionVn iD1 Wn jD1 xij, known as the AND-OR tree, has approximate degree˝.n/: This lower bound is tight and closes a line of research on the problem, the best previous bound being ˝.n0:75/. More generally, we prove that the function
The ε-approximate degree of a Boolean function f:{−1,1}n→{−1,1} is the minimum degree of a real polynomial that approximates f to within ε in the ℓ∞ 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 Θ(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.
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 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.
A Nearly Optimal Lower Bound on the Approximate Degree of AC0
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 AC0 function 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.