A Tight Lower Bound on Certificate Complexity in Terms of Block Sensitivity and Sensitivity

Andris Ambainis, Krišjānis Prūsis

Sensitivity, certificate complexity and block sensitivity are widely used Boolean function complexity measures. A longstanding open problem, proposed by Nisan and Szegedy, is wheth…