ECCC-Report TR20-134https://eccc.weizmann.ac.il/report/2020/134Comments and Revisions published for TR20-134en-usWed, 09 Sep 2020 02:39:46 +0300
Paper TR20-134
| Tight Bounds on Sensitivity and Block Sensitivity of Some Classes of Transitive Functions |
Anna Gal,
Siddhesh Chaubal
https://eccc.weizmann.ac.il/report/2020/134Nisan and Szegedy conjectured that block sensitivity is at most
polynomial in sensitivity for any Boolean function.
Until a recent breakthrough of Huang, the conjecture had been
wide open in the general case,
and was proved only for a few special classes
of Boolean functions.
Huang's result implies that block sensitivity is at most
the 4th power of sensitivity for any Boolean function.
It remains open if a tighter relationship between
sensitivity and block sensitivity holds for arbitrary Boolean functions;
the largest known gap between these measures is quadratic.
We prove tighter bounds showing that block sensitivity is at most
3rd power, and in some cases at most square of sensitivity for
subclasses of transitive functions,
defined by various properties of their DNF (or CNF) representation.
Our results improve and extend previous results regarding
transitive functions. We obtain these results by
proving tight (up to constant factors) lower bounds on the
smallest possible sensitivity of functions in these classes.
In another line of research, it has also been examined what is the
smallest possible block sensitivity of transitive functions.
Our results yield tight (up to constant factors) lower bounds
on the block sensitivity of the classes we consider.Wed, 09 Sep 2020 02:39:46 +0300https://eccc.weizmann.ac.il/report/2020/134