1Shimane University (1060 Nishikawatsu-cho, Matsue-shi, Shimane 690-8504, Japan - Japan)
Abstract : 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.
https://hal.inria.fr/hal-01402033 Contributor : Hal IfipConnect in order to contact the contributor Submitted on : Thursday, November 24, 2016 - 10:49:05 AM Last modification on : Thursday, November 24, 2016 - 11:14:11 AM Long-term archiving on: : Tuesday, March 21, 2017 - 3:35:01 AM