Skip to Main content Skip to Navigation
Conference papers

Sensitivity, Block Sensitivity, and Certificate Complexity of Unate Functions and Read-Once Functions

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.
Document type :
Conference papers
Complete list of metadata

Cited literature [10 references]  Display  Hide  Download

https://hal.inria.fr/hal-01402033
Contributor : Hal Ifip <>
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

File

978-3-662-44602-7_9_Chapter.pd...
Files produced by the author(s)

Licence


Distributed under a Creative Commons Attribution 4.0 International License

Identifiers

Citation

Hiroki Morizumi. Sensitivity, Block Sensitivity, and Certificate Complexity of Unate Functions and Read-Once Functions. 8th IFIP International Conference on Theoretical Computer Science (TCS), Sep 2014, Rome, Italy. pp.104-110, ⟨10.1007/978-3-662-44602-7_9⟩. ⟨hal-01402033⟩

Share

Metrics

Record views

92

Files downloads

297