__
TR20-134 | 9th September 2020 02:39
__

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

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