The approximate degree of disjunction

The disjunction OR_n of n bits has approximate degree Θ(√n) [NS94].

• Lower bound: OR_n is sensitive to every bit at the all-false input, so bs(OR_n) = n (QueryComplexity.blockSensitivity_threshold_one_right) and n ≤ 6 adeg(OR_n)² by the Nisan–Szegedy bound (QueryComplexity.card_le_six_mul_approxDegree_threshold_one_right_sq).
• Upper bound: a Chebyshev polynomial T_d stays in [-1, 1] on [-1, 1] and grows at least like 1 + d² μ at 1 + μ (Polynomial.Chebyshev.one_add_sq_mul_le_eval_T). With u(k) = (n - k) / (n - 1), the polynomial Q(k) = 1 - T_d(u(k)) / T_d(u(0)) vanishes at 0 and is within 1 / T_d(1 + 1/(n - 1)) ≤ 1 / 3 of 1 at k = 1, …, n once d² ≥ 2 (n - 1); evaluated at the weight it has degree at most d on the cube (QueryComplexity.approxDegree_threshold_one_right_le). So adeg(OR_n) ≤ ⌊√(2n)⌋ + 1 (QueryComplexity.approxDegree_threshold_one_right_le_sqrt).

Main results

• Polynomial.Chebyshev.one_add_sq_mul_le_eval_T: T_n(1 + μ) ≥ 1 + n² μ for μ ≥ 0.
• Cslib.QueryComplexity.card_le_six_mul_approxDegree_threshold_one_right_sq: n ≤ 6 adeg(OR_n)².
• Cslib.QueryComplexity.approxDegree_threshold_one_right_le: adeg(OR_n) ≤ d whenever 2n ≤ d² + 1.
• Cslib.QueryComplexity.approxDegree_threshold_one_right_le_sqrt: adeg(OR_n) ≤ ⌊√(2n)⌋ + 1.

References

• N. Nisan, M. Szegedy, On the degree of Boolean functions as real polynomials
• H. Buhrman, R. de Wolf, Complexity measures and decision tree complexity: a survey

theorem Polynomial.Chebyshev.one_add_sq_mul_le_eval_T (n : ℕ) {μ : ℝ} (hμ : 0 ≤ μ) : 1 + ↑n ^ 2 * μ ≤ eval (1 + μ) (T ℝ ↑n)

Growth of Chebyshev polynomials beyond 1: T_n(1 + μ) ≥ 1 + n² μ for μ ≥ 0.

theorem Cslib.QueryComplexity.card_le_six_mul_approxDegree_threshold_one_right_sq {n : ℕ} : n ≤ 6 * approxDegree (1 / 3) (threshold n 1) ^ 2

The approximate degree of disjunction is at least √(n / 6): n ≤ 6 adeg(OR_n)².

theorem Cslib.QueryComplexity.approxDegree_threshold_one_right_le {n d : ℕ} (hd : 2 * n ≤ d ^ 2 + 1) : approxDegree (1 / 3) (threshold n 1) ≤ d

The approximate degree of disjunction is at most √(2n): adeg(OR_n) ≤ d whenever 2n ≤ d² + 1, by a rescaled Chebyshev polynomial of degree d evaluated at the weight.

theorem Cslib.QueryComplexity.approxDegree_threshold_one_right_le_sqrt {n : ℕ} : approxDegree (1 / 3) (threshold n 1) ≤ (2 * n).sqrt + 1

adeg(OR_n) ≤ ⌊√(2n)⌋ + 1.