Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR20-134 | 9th September 2020 02:39

Tight Bounds on Sensitivity and Block Sensitivity of Some Classes of Transitive Functions

RSS-Feed




TR20-134
Authors: Siddhesh Chaubal, Anna Gal
Publication: 9th September 2020 02:39
Downloads: 657
Keywords: 


Abstract:

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



ISSN 1433-8092 | Imprint