New Constructions with Quadratic Separation between Sensitivity and Block Sensitivity

摘要

Nisan and Szegedy conjectured that block sensitivity is at most polynomial in sensitivity for any Boolean function. There is a huge gap between the best known upper bound on block sensitivity in terms of sensitivity - which is exponential, and the best known separating examples - which give only a quadratic separation between block sensitivity and sensitivity.In this paper we give various new constructions of families of Boolean functions that exhibit quadratic separation between sensitivity and block sensitivity. Some of our constructions match the current largest separation between sensitivity and block sensitivity by Ambainis and Sun. Our constructions have several novel aspects. We use more general function compositions instead of just OR-composition, and give constructions based on algebraic operations. In addition, we give the first direct constructions of families of Boolean functions that have both 0-block sensitivity and 1-block sensitivity quadratically larger than sensitivity.