Sensitivity, Block Sensitivity, and Certificate Complexity of Unate Functions and Read-Once Functions - Theoretical Computer Science
Conference Papers Year : 2014

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

Hiroki Morizumi
  • Function : Author
  • PersonId : 994201

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.
Fichier principal
Vignette du fichier
978-3-662-44602-7_9_Chapter.pdf (95.66 Ko) Télécharger le fichier
Origin Files produced by the author(s)
Loading...

Dates and versions

hal-01402033 , version 1 (24-11-2016)

Licence

Identifiers

Cite

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⟩
49 View
222 Download

Altmetric

Share

More