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] and D(f) ≤ C(f) bs(f) [BBC+01], which give D(f) ≤ s(f) bs(f)² (DecisionTree.complexity_le_sensitivity_mul_blockSensitivity_sq), this bounds certificate and decision tree complexity polynomially in sensitivity: C(f) ≤ 2 s(f)⁵ and D(f) ≤ 4 s(f)⁹.

Main results

• Cslib.QueryComplexity.certificateComplexity_le_two_mul_sensitivity_pow_five: C(f) ≤ 2 s(f)⁵.
• Cslib.DecisionTree.complexity_le_four_mul_sensitivity_pow_nine: D(f) ≤ 4 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
• R. Beals, H. Buhrman, R. Cleve, M. Mosca, R. de Wolf, Quantum lower bounds by polynomials

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_four_mul_sensitivity_pow_nine {n : ℕ} (f : BooleanFunction n) : complexity f ≤ 4 * BitString.sensitivity f ^ 9

Decision tree complexity is polynomial in sensitivity: D(f) ≤ 4 s(f)⁹, from D(f) ≤ s(f) bs(f)² and bs(f) ≤ 2 s(f)⁴.