Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Siddhesh Chaubal:

TR18-205 | 3rd December 2018
Siddhesh Chaubal, Anna Gal

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

ISSN 1433-8092 | Imprint