Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > BOOLEAN FUNCTION PARAMETERS:
Reports tagged with Boolean function parameters:
TR17-192 | 15th December 2017
Krishnamoorthy Dinesh, Jayalal Sarma

Alternation, Sparsity and Sensitivity : Bounds and Exponential Gaps

Revisions: 1

The well-known Sensitivity Conjecture regarding combinatorial complexity measures on Boolean functions states that for any Boolean function $f:\{0,1\}^n \to \{0,1\}$, block sensitivity of $f$ is polynomially related to sensitivity of $f$ (denoted by $\mathbf{sens}(f)$). From the complexity theory side, the XOR Log-Rank Conjecture states that for any Boolean function, \$f:\{0,1\}^n ... more >>>

ISSN 1433-8092 | Imprint