Lower bounds on randomized decision tree complexity

Block sensitivity and approximate degree bound randomized decision tree complexity below, so deterministic and bounded-error randomized decision tree complexity are polynomially related [Nis91].

Block sensitivity (QueryComplexity.one_sub_two_mul_mul_blockSensitivity_le_randomizedComplexity). Let μ compute f with error ε, and let x have b = bs(f) pairwise disjoint sensitive blocks B₁, …, B_b. A tree t that queries no variable of Bⱼ on input x reaches the same leaf on x and on x with Bⱼ flipped, while f differs there, so t errs on one of the two inputs. The blocks are disjoint, so t queries variables of at most depth t of them, and errs on x or on x with Bⱼ flipped for every other block. Averaging over t drawn from μ, b ≤ depth μ + ∑ⱼ (ε + ε), that is (1 - 2ε) bs(f) ≤ R_ε(f); for ε = 1/3, bs(f) ≤ 3 R(f). With D(f) ≤ bs(f)³ [BBC+01] this gives D(f) ≤ 27 R(f)³.

Approximate degree (QueryComplexity.approxDegree_le_randomizedComplexity). The probability that a tree drawn from μ outputs 1 on x is an average of functions of degree at most the depth of μ (DecisionTree.comp_eval_mem_lowDegree), so has degree at most depth μ, and it is within ε of f when μ computes f with error ε. So adeg_ε(f) ≤ R_ε(f) [BdW02].

Main results

• Cslib.QueryComplexity.one_sub_two_mul_mul_blockSensitivity_le_randomizedComplexity: (1 - 2ε) bs(f) ≤ R_ε(f) for ε ≥ 0.
• Cslib.QueryComplexity.blockSensitivity_le_three_mul_randomizedComplexity: bs(f) ≤ 3 R(f).
• Cslib.QueryComplexity.approxDegree_le_randomizedComplexity: adeg_ε(f) ≤ R_ε(f).
• Cslib.RandomizedDecisionTree.Computes.one_sub_two_mul_mul_blockSensitivity_le_depth, Cslib.RandomizedDecisionTree.Computes.approxDegree_le_depth: the same bounds for the depth of one randomized decision tree computing f with error ε.
• Cslib.DecisionTree.one_sub_two_mul_pow_three_mul_complexity_le: (1 - 2ε)³ D(f) ≤ R_ε(f)³ for ε ≥ 0.
• Cslib.DecisionTree.complexity_le_mul_randomizedComplexity_pow_three: D(f) ≤ 27 R(f)³.

References

• N. Nisan, CREW PRAMs and decision trees
• R. Beals, H. Buhrman, R. Cleve, M. Mosca, R. de Wolf, Quantum lower bounds by polynomials
• H. Buhrman, R. de Wolf, Complexity measures and decision tree complexity: a survey

theorem Cslib.RandomizedDecisionTree.Computes.one_sub_two_mul_mul_blockSensitivity_le_depth {n : ℕ} {f : BooleanFunction n} {μ : RandomizedDecisionTree (Fin n) Bool} {ε : ℝ} (h : μ.Computes ε f) : (1 - 2 * ε) * ↑(QueryComplexity.blockSensitivity f) ≤ ↑μ.depth

Nisan's bound for one randomized decision tree: if μ computes f with error ε, then (1 - 2ε) bs(f) ≤ depth μ.

theorem Cslib.RandomizedDecisionTree.Computes.approxDegree_le_depth {n : ℕ} {f : BooleanFunction n} {μ : RandomizedDecisionTree (Fin n) Bool} {ε : ℝ} (h : μ.Computes ε f) : QueryComplexity.approxDegree ε f ≤ μ.depth

A randomized decision tree computing f with error ε gives a real function of degree at most its depth within ε of f: the probability that the tree drawn outputs 1.

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

Nisan's bound: (1 - 2ε) bs(f) ≤ R_ε(f) for ε ≥ 0.

theorem Cslib.QueryComplexity.blockSensitivity_le_three_mul_randomizedComplexity {n : ℕ} (f : BooleanFunction n) : blockSensitivity f ≤ 3 * randomizedComplexity (1 / 3) f

Nisan's bound for bounded error: bs(f) ≤ 3 R(f), for R = R_{1/3}.

theorem Cslib.QueryComplexity.approxDegree_le_randomizedComplexity {n : ℕ} (ε : ℝ) (f : BooleanFunction n) : approxDegree ε f ≤ randomizedComplexity ε f

Approximate degree is at most randomized complexity: adeg_ε(f) ≤ R_ε(f).

theorem Cslib.DecisionTree.one_sub_two_mul_pow_three_mul_complexity_le {n : ℕ} {ε : ℝ} (hε : 0 ≤ ε) (f : BooleanFunction n) : (1 - 2 * ε) ^ 3 * ↑(complexity f) ≤ ↑(QueryComplexity.randomizedComplexity ε f) ^ 3

(1 - 2ε)³ D(f) ≤ R_ε(f)³ for ε ≥ 0, from D(f) ≤ bs(f)³ and Nisan's bound.

theorem Cslib.DecisionTree.complexity_le_mul_randomizedComplexity_pow_three {n : ℕ} (f : BooleanFunction n) : complexity f ≤ 27 * QueryComplexity.randomizedComplexity (1 / 3) f ^ 3

Deterministic and randomized decision tree complexity are polynomially related [Nis91]: D(f) ≤ 27 R(f)³ for the bounded-error randomized complexity R = R_{1/3}, from bs(f) ≤ 3 R(f) and D(f) ≤ bs(f)³.