Block Sensitivity can exceed Spectral Sensitivity Squared

Alexander Meiburg

The spectral sensitivity $\hat{I}»(f)$ of a Boolean function is the largest eigenvalue of the adjacency matrix of its sensitivity graph. It lower-bounds every standard measure of query c…