Relations between block sensitivity, certificate and decision tree complexity

Block sensitivity bounds certificate and decision tree complexity polynomially, so that the three are polynomially related [BdW02]. For a value b, the one-sided measures s_b(f), bs_b(f) and C_b(f) are the largest sensitivity, block sensitivity and certificate complexity of f at an input of value b.

• C(f) ≤ s(f) bs(f), due to Nisan [Nis91] (QueryComplexity.certificateComplexity_le_sensitivity_mul_blockSensitivity). Take a largest family of pairwise disjoint minimal sensitive blocks at x. Every coordinate of a block B of it is sensitive at x with B flipped, an input of value ¬f(x), so |B| ≤ s_{¬f(x)}(f) (QueryComplexity.IsMinimalSensitiveBlock.card_le_sensitivityFor). The union of the family is a certificate for x: an input agreeing with x on it but with a different value differs from x on a sensitive block disjoint from the family, which contains a minimal one and would enlarge the family. This gives the one-sided form C_b(f) ≤ s_{¬b}(f) bs_b(f) (QueryComplexity.certificateComplexityFor_le_sensitivityFor_mul_blockSensitivityFor).
• D(f) ≤ bs₀(f) C₁(f) ≤ C(f) bs(f) (DecisionTree.complexity_le_blockSensitivityFor_mul_certificateComplexityFor). This is a one-sided form of the bound D(f) ≤ C₁(f) bs(f) of Beals, Buhrman, Cleve, Mosca and de Wolf [BBC+01] ([BdW02], Theorem 11). Query a smallest certificate of an input of value 1. Every input of value 0 of the function restricted by the answers has one more sensitive block in the original function, the coordinates of the certificate on which it differs from the input of value 1, so its block sensitivity has dropped.

With D(¬f) = D(f) this turns D(f) ≤ bs₀(f) C₁(f) into its dual D(f) ≤ bs₁(f) C₀(f) (DecisionTree.complexity_le_blockSensitivityFor_not_mul_certificateComplexityFor), hence D(f) ≤ min(C₀(f), C₁(f)) bs(f), and with the one-sided Nisan bound it gives D(f) ≤ bs_{¬b}(f) s_{¬b}(f) bs_b(f), in particular D(f) ≤ bs₀(f) bs₁(f) s(f). With C(f) ≤ s(f) bs(f) ≤ bs(f)² it gives D(f) ≤ s(f) bs(f)² ≤ bs(f)³ (DecisionTree.complexity_le_sensitivity_mul_blockSensitivity_sq, DecisionTree.complexity_le_blockSensitivity_pow_three; [BdW02], Corollary 1).

Main results

• Cslib.QueryComplexity.certificateComplexityAt_le_sensitivityFor_mul_blockSensitivityAt: C(f, x) ≤ s_{¬f(x)}(f) bs(f, x).
• Cslib.QueryComplexity.certificateComplexityFor_le_sensitivityFor_mul_blockSensitivityFor: C_b(f) ≤ s_{¬b}(f) bs_b(f).
• Cslib.QueryComplexity.certificateComplexityAt_le_sensitivity_mul_blockSensitivityAt: C(f, x) ≤ s(f) bs(f, x).
• Cslib.QueryComplexity.certificateComplexity_le_sensitivity_mul_blockSensitivity: C(f) ≤ s(f) bs(f).
• Cslib.QueryComplexity.certificateComplexity_le_blockSensitivity_sq: C(f) ≤ bs(f)².
• Cslib.DecisionTree.complexity_le_blockSensitivityFor_mul_certificateComplexityFor: D(f) ≤ bs₀(f) C₁(f).
• Cslib.DecisionTree.complexity_le_blockSensitivityFor_not_mul_certificateComplexityFor: D(f) ≤ bs_{¬b}(f) C_b(f).
• Cslib.DecisionTree.complexity_le_min_certificateComplexityFor_mul_blockSensitivity: D(f) ≤ min(C₀(f), C₁(f)) bs(f).
• Cslib.DecisionTree.complexity_le_blockSensitivityFor_mul_sensitivityFor_mul_blockSensitivityFor: D(f) ≤ bs_{¬b}(f) s_{¬b}(f) bs_b(f).
• Cslib.DecisionTree.complexity_le_blockSensitivityFor_mul_blockSensitivityFor_mul_sensitivity: D(f) ≤ bs₀(f) bs₁(f) s(f).
• Cslib.DecisionTree.complexity_le_certificateComplexity_mul_blockSensitivity: D(f) ≤ C(f) bs(f).
• Cslib.DecisionTree.complexity_le_sensitivity_mul_blockSensitivity_sq: D(f) ≤ s(f) bs(f)².
• Cslib.DecisionTree.complexity_le_blockSensitivity_pow_three: D(f) ≤ bs(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.BitString.flipBlock_filter_ne {n : ℕ} (x y : BitString n) : flipBlock {i : Fin n | y i ≠ x i} x = y

Flipping the coordinates on which y differs from x turns x into y.

C(f) ≤ s(f) bs(f)

theorem Cslib.QueryComplexity.IsSensitiveBlock.exists_isMinimalSensitiveBlock_subset {n : ℕ} {f : BooleanFunction n} {x : BitString n} {B : Block n} (hB : IsSensitiveBlock f x B) : ∃ C ⊆ B, IsMinimalSensitiveBlock f x C

A sensitive block contains a minimal sensitive block.

theorem Cslib.QueryComplexity.IsSensitiveBlock.nonempty {n : ℕ} {f : BooleanFunction n} {x : BitString n} {B : Block n} (hB : IsSensitiveBlock f x B) : Finset.Nonempty B

A sensitive block is nonempty.

theorem Cslib.QueryComplexity.IsMinimalSensitiveBlock.card_le_sensitivityFor {n : ℕ} {f : BooleanFunction n} {x : BitString n} {B : Block n} (hB : IsMinimalSensitiveBlock f x B) : Finset.card B ≤ BitString.sensitivityFor f !f x

A minimal sensitive block at x has at most s_{¬f(x)}(f) coordinates: they are all sensitive at x with the block flipped, where f has the other value.

theorem Cslib.QueryComplexity.certificateComplexityAt_le_sensitivityFor_mul_blockSensitivityAt {n : ℕ} (f : BooleanFunction n) (x : BitString n) : certificateComplexityAt f x ≤ (BitString.sensitivityFor f !f x) * blockSensitivityAt f x

One-sided Nisan bound at an input: C(f, x) ≤ s_{¬f(x)}(f) bs(f, x).

theorem Cslib.QueryComplexity.certificateComplexityAt_le_sensitivity_mul_blockSensitivityAt {n : ℕ} (f : BooleanFunction n) (x : BitString n) : certificateComplexityAt f x ≤ BitString.sensitivity f * blockSensitivityAt f x

Nisan's bound at an input: C(f, x) ≤ s(f) bs(f, x).

theorem Cslib.QueryComplexity.certificateComplexity_le_sensitivity_mul_blockSensitivity {n : ℕ} (f : BooleanFunction n) : certificateComplexity f ≤ BitString.sensitivity f * blockSensitivity f

Nisan's bound: C(f) ≤ s(f) bs(f).

theorem Cslib.QueryComplexity.certificateComplexity_le_blockSensitivity_sq {n : ℕ} (f : BooleanFunction n) : certificateComplexity f ≤ blockSensitivity f ^ 2

C(f) ≤ bs(f)².

theorem Cslib.QueryComplexity.certificateComplexityFor_le_sensitivityFor_mul_blockSensitivityFor {n : ℕ} (f : BooleanFunction n) (b : Bool) : certificateComplexityFor f b ≤ (BitString.sensitivityFor f !b) * blockSensitivityFor f b

One-sided Nisan bound: C_b(f) ≤ s_{¬b}(f) bs_b(f).

Restricting by answers on a sensitive block

theorem Cslib.QueryComplexity.blockSensitivityAt_comp_piecewise_add_one_le {n : ℕ} {f : BooleanFunction n} {S B₀ : Finset (Fin n)} (a z : BitString n) (hB₀S : B₀ ⊆ S) (hB₀ : IsSensitiveBlock f (S.piecewise a z) B₀) : blockSensitivityAt (fun (y : BitString n) => f (S.piecewise a y)) z + 1 ≤ blockSensitivityAt f (S.piecewise a z)

Restricting the coordinates in S lowers block sensitivity at an input whenever the filled input has a sensitive block contained in S. This block can be added to every sensitive family of the restricted function after removing the fixed coordinates from its blocks.

theorem Cslib.DecisionTree.complexity_le_blockSensitivityFor_mul_certificateComplexityFor {n : ℕ} (f : BooleanFunction n) : complexity f ≤ QueryComplexity.blockSensitivityFor f false * QueryComplexity.certificateComplexityFor f true

Decision tree complexity from block sensitivity and certificates: D(f) ≤ bs₀(f) C₁(f), a one-sided form of the bound D(f) ≤ C₁(f) bs(f) of Beals, Buhrman, Cleve, Mosca and de Wolf [BBC+01].

theorem Cslib.DecisionTree.complexity_le_blockSensitivityFor_not_mul_certificateComplexityFor {n : ℕ} (f : BooleanFunction n) (b : Bool) : complexity f ≤ (QueryComplexity.blockSensitivityFor f !b) * QueryComplexity.certificateComplexityFor f b

Decision tree complexity from one-sided measures: D(f) ≤ bs_{¬b}(f) C_b(f) for either value b. For b = 1 this is D(f) ≤ bs₀(f) C₁(f), a one-sided form of the bound of Beals, Buhrman, Cleve, Mosca and de Wolf [BBC+01]; negating the function gives the dual D(f) ≤ bs₁(f) C₀(f).

theorem Cslib.DecisionTree.complexity_le_certificateComplexityFor_mul_blockSensitivity {n : ℕ} (f : BooleanFunction n) (b : Bool) : complexity f ≤ QueryComplexity.certificateComplexityFor f b * QueryComplexity.blockSensitivity f

D(f) ≤ C_b(f) bs(f) for either value b [BBC+01].

theorem Cslib.DecisionTree.complexity_le_min_certificateComplexityFor_mul_blockSensitivity {n : ℕ} (f : BooleanFunction n) : complexity f ≤ min (QueryComplexity.certificateComplexityFor f false) (QueryComplexity.certificateComplexityFor f true) * QueryComplexity.blockSensitivity f

D(f) ≤ min(C₀(f), C₁(f)) bs(f).

theorem Cslib.DecisionTree.complexity_le_blockSensitivityFor_mul_sensitivityFor_mul_blockSensitivityFor {n : ℕ} (f : BooleanFunction n) (b : Bool) : complexity f ≤ ((QueryComplexity.blockSensitivityFor f !b) * BitString.sensitivityFor f !b) * QueryComplexity.blockSensitivityFor f b

D(f) ≤ bs_{¬b}(f) s_{¬b}(f) bs_b(f), from D(f) ≤ bs_{¬b}(f) C_b(f) and the one-sided Nisan bound.

theorem Cslib.DecisionTree.complexity_le_blockSensitivityFor_mul_blockSensitivityFor_mul_sensitivity {n : ℕ} (f : BooleanFunction n) : complexity f ≤ QueryComplexity.blockSensitivityFor f false * QueryComplexity.blockSensitivityFor f true * BitString.sensitivity f

D(f) ≤ bs₀(f) bs₁(f) s(f).

theorem Cslib.DecisionTree.complexity_le_certificateComplexity_mul_blockSensitivity {n : ℕ} (f : BooleanFunction n) : complexity f ≤ QueryComplexity.certificateComplexity f * QueryComplexity.blockSensitivity f

D(f) ≤ C(f) bs(f) [BBC+01].

theorem Cslib.DecisionTree.complexity_le_sensitivity_mul_blockSensitivity_sq {n : ℕ} (f : BooleanFunction n) : complexity f ≤ BitString.sensitivity f * QueryComplexity.blockSensitivity f ^ 2

D(f) ≤ s(f) bs(f)², from D(f) ≤ C(f) bs(f) and Nisan's C(f) ≤ s(f) bs(f).

theorem Cslib.DecisionTree.complexity_le_blockSensitivity_pow_three {n : ℕ} (f : BooleanFunction n) : complexity f ≤ QueryComplexity.blockSensitivity f ^ 3

Decision tree complexity is at most the cube of block sensitivity: D(f) ≤ bs(f)³ [BBC+01].