Sensitivity, Block Sensitivity, and Certificate Complexity of Unate Functions and Read-Once Functions
Hiroki Morizumi · 2013
Sensitivity, block sensitivity, and certificate complexity are complexity measures for Boolean functions. In this paper, we prove that these three complexity measures are equal to each other if a Boolean function is a unate function or a read-once function. We also prove \(\sqrt{n}\) tight lower bounds for the three complexity measures of read-once functions. As an application of our results, the decision tree complexity of unate functions and read-once functions is upper bounded by the square of the sensitivity of the function.