Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > DECISION TREE SIZE:
Reports tagged with Decision tree size:
TR26-010 | 1st February 2026
Sourav Chakraborty, Anna Gal

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

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




ISSN 1433-8092 | Imprint