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

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 the answers to a certificate

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].