Polynomial bounds in terms of sensitivity

Huang's theorem deg(f) ≤ s(f)² [Hua19] and the Nisan–Szegedy bound bs(f) ≤ 2 deg(f)² [NS94] give bs(f) ≤ 2 s(f)⁴ (QueryComplexity.blockSensitivity_le_two_mul_sensitivity_pow_four). Combined with Nisan's C(f) ≤ s(f) bs(f) [Nis91], this gives C(f) ≤ 2 s(f)⁵. Midrijanis's cubic degree bound D(f) ≤ 2 deg(f)³ [Mid04] and Huang's theorem give the sharper decision tree bound D(f) ≤ 2 s(f)⁶.

Main results

• Cslib.QueryComplexity.certificateComplexity_le_two_mul_sensitivity_pow_five: C(f) ≤ 2 s(f)⁵.
• Cslib.DecisionTree.complexity_le_two_mul_sensitivity_pow_six: D(f) ≤ 2 s(f)⁶.

References

• H. Huang, Induced subgraphs of hypercubes and a proof of the Sensitivity Conjecture
• N. Nisan, M. Szegedy, On the degree of Boolean functions as real polynomials
• N. Nisan, CREW PRAMs and decision trees
• G. Midrijanis, Exact quantum query complexity for total Boolean functions

theorem Cslib.QueryComplexity.certificateComplexity_le_two_mul_sensitivity_pow_five {n : ℕ} (f : BooleanFunction n) : certificateComplexity f ≤ 2 * BitString.sensitivity f ^ 5

C(f) ≤ 2 s(f)⁵, from Nisan's C(f) ≤ s(f) bs(f) and bs(f) ≤ 2 s(f)⁴.

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

Decision tree complexity is polynomial in sensitivity: D(f) ≤ 2 s(f)⁶, from Midrijanis's D(f) ≤ 2 deg(f)³ and Huang's deg(f) ≤ s(f)².