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