Tighter Relations between Sensitivity and Other Complexity Measures

Part of book or chapter of book, Preprint English OPEN
Ambainis, Andris; Bavarian, Mohammad; Gao, Yihan; Mao, Jieming; Sun, Xiaoming; Zuo, Song;

Sensitivity conjecture is a longstanding and fundamental open problem in the area of complexity measures of Boolean functions and decision tree complexity. The conjecture postulates that the maximum sensitivity of a Boolean function is polynomially related to other majo... View more
Share - Bookmark