Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR18-205 | 3rd December 2018 01:53

New Constructions with Quadratic Separation between Sensitivity and Block Sensitivity


Authors: Siddhesh Chaubal, Anna Gal
Publication: 3rd December 2018 01:54
Downloads: 914


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.

ISSN 1433-8092 | Imprint