Sensitivity of $m$-ary functions and low degree partitions of Hamming graphs

Sara Asensio, Ignacio García-Marco, Kolja Knauer

The study of complexity measures of Boolean functions led Nisan and Szegedy to state the sensitivity conjecture in 1994, claiming a polynomial relation between degree and sensitivi…