Documentation

Complexity.Computability.QueryComplexity.NisanSzegedy

The Nisan–Szegedy bounds #

Block sensitivity is at most quadratic in the degree and in the approximate degree: bs(f) ≤ 2 deg(f)² and bs(f) ≤ 6 adeg(f)² with adeg = adeg_{1/3} [NS94].

Both follow from one argument (QueryComplexity.one_sub_two_mul_mul_blockSensitivity_le). Let a real function p of degree at most D be within ε < 1/2 of f, and let x have b = bs(f) pairwise disjoint sensitive blocks B₁, …, B_b. Normalizing so that f(x) reads as 0, the function g(y) = p(x ⊕ ⋃_{yⱼ = 1} Bⱼ) on {0,1}ᵇ still has degree at most D (BitString.comp_mem_lowDegree), lies in [-ε, 1 + ε], is at most ε at 0 and at least 1 - ε at each unit vector. Its Minsky–Papert symmetrization q (BitString.exists_natDegree_le_eval_eq_layerAverage) is a univariate polynomial of degree at most D with the same bounds at the integers 0, …, b, and the mean value theorem gives a point of [0, 1] where q' ≥ 1 - 2ε. The Nisan–Szegedy lemma, a consequence of Markov's inequality (Polynomial.mul_le_sq_mul_of_le_abs_eval_derivative), then gives (1 - 2ε) b ≤ D² (1 - 2ε + 1 + 2ε) = 2 D².

With Huang's theorem deg(f) ≤ s(f)² this gives bs(f) ≤ 2 s(f)⁴, and with D(f) ≤ bs(f)³ [BBC+01] it gives D(f) ≤ 8 deg(f)⁶ and D(f) ≤ 216 adeg(f)⁶: decision tree complexity, degree and approximate degree are polynomially related.

Main results #

References #

source
theorem Cslib.QueryComplexity.one_sub_two_mul_mul_blockSensitivity_le_of_mem_lowDegree {n : ℕ} {f : BooleanFunction n} {p : BitString n → ℝ} {D : ℕ} (hp : p ∈ BitString.lowDegree ℝ (Fin n) D) {ε : ℝ} (hpf : ∀ (x : BitString n), |p x - BitString.bitVal ℝ (f x)| ≤ ε) :
(1 - 2 * ε) * ↑(blockSensitivity f) ≤ 2 * ↑D ^ 2

The Nisan–Szegedy argument: if a real function of degree at most D is within ε of f at every input, then (1 - 2ε) bs(f) ≤ 2 D².

source
theorem Cslib.QueryComplexity.blockSensitivity_le_two_mul_degree_sq {n : ℕ} (f : BooleanFunction n) :
blockSensitivity f ≤ 2 * degree f ^ 2

Nisan–Szegedy: bs(f) ≤ 2 deg(f)².

source
theorem Cslib.QueryComplexity.one_sub_two_mul_mul_blockSensitivity_le {n : ℕ} {ε : ℝ} (hε : 0 ≤ ε) (f : BooleanFunction n) :
(1 - 2 * ε) * ↑(blockSensitivity f) ≤ 2 * ↑(approxDegree ε f) ^ 2

Nisan–Szegedy for approximate degree: (1 - 2ε) bs(f) ≤ 2 adeg_ε(f)² for ε ≥ 0.

source
theorem Cslib.QueryComplexity.blockSensitivity_le_six_mul_approxDegree_sq {n : ℕ} (f : BooleanFunction n) :
blockSensitivity f ≤ 6 * approxDegree (1 / 3) f ^ 2

Nisan–Szegedy: bs(f) ≤ 6 adeg(f)², for the approximate degree adeg = adeg_{1/3}.

source
theorem Cslib.QueryComplexity.blockSensitivity_le_two_mul_sensitivity_pow_four {n : ℕ} (f : BooleanFunction n) :
blockSensitivity f ≤ 2 * BitString.sensitivity f ^ 4

bs(f) ≤ 2 s(f)⁴, from Nisan–Szegedy and Huang's theorem deg(f) ≤ s(f)².

source
theorem Cslib.DecisionTree.complexity_le_eight_mul_degree_pow_six {n : ℕ} (f : BooleanFunction n) :
complexity f ≤ 8 * QueryComplexity.degree f ^ 6

D(f) ≤ 8 deg(f)⁶, from D(f) ≤ bs(f)³ and bs(f) ≤ 2 deg(f)².

source
theorem Cslib.DecisionTree.complexity_le_mul_approxDegree_pow_six {n : ℕ} (f : BooleanFunction n) :
complexity f ≤ 216 * QueryComplexity.approxDegree (1 / 3) f ^ 6

D(f) ≤ 216 adeg(f)⁶ for the approximate degree adeg = adeg_{1/3}, from D(f) ≤ bs(f)³ and bs(f) ≤ 6 adeg(f)².