%0 Conference Proceedings
%T Sensitivity, Block Sensitivity, and Certificate Complexity of Unate Functions and Read-Once Functions
%+ Shimane University
%A Morizumi, Hiroki
%Z Part 1: Track A: Algorithms, Complexity and Models of Computation
%< avec comité de lecture
%( Lecture Notes in Computer Science
%B 8th IFIP International Conference on Theoretical Computer Science (TCS)
%C Rome, Italy
%Y Josep Diaz
%Y Ivan Lanese
%Y Davide Sangiorgi
%I Springer
%3 Theoretical Computer Science
%V LNCS-8705
%P 104-110
%8 2014-09-01
%D 2014
%R 10.1007/978-3-662-44602-7_9
%Z Computer Science [cs]Conference papers
%X 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.
%G English
%Z TC 1
%Z TC 2
%Z WG 2.2
%2 https://inria.hal.science/hal-01402033/document
%2 https://inria.hal.science/hal-01402033/file/978-3-662-44602-7_9_Chapter.pdf
%L hal-01402033
%U https://inria.hal.science/hal-01402033
%~ IFIP-LNCS
%~ IFIP
%~ IFIP-TC
%~ IFIP-TC2
%~ IFIP-LNCS-8705
%~ IFIP-TCS
%~ IFIP-WG2-2