Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR26-010 | 1st February 2026 09:53

Nearly Tight Bounds on the Block Number of Boolean Functions in Terms of Sensitivity

RSS-Feed




TR26-010
Authors: Sourav Chakraborty, Anna Gal
Publication: 1st February 2026 09:54
Downloads: 32
Keywords: 


Abstract:

This paper explores the previously studied measure called block number of Boolean functions, that counts the maximum possible number of minimal sensitive blocks for any input. We present close to tight upper bounds on the block number in terms of the function’s sensitivity and the allowed block size, improving previous bounds by a quadratic factor. Moreover, our bound on the block number yields sharper upper bounds on DNF size and decision tree size. We obtain these results by introducing and estimating a novel measure called brick number, which not only upper bounds the block number but also leads to a new characterization of block sensitivity.



ISSN 1433-8092 | Imprint