Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with transitive functions:
TR20-134 | 9th September 2020
Siddhesh Chaubal, Anna Gal

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

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

ISSN 1433-8092 | Imprint