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.
Type de document :
Communication dans un congrès
Josep Diaz; Ivan Lanese; Davide Sangiorgi. 8th IFIP International Conference on Theoretical Computer Science (TCS), Sep 2014, Rome, Italy. Springer, Lecture Notes in Computer Science, LNCS-8705, pp.104-110, 2014, Theoretical Computer Science. 〈10.1007/978-3-662-44602-7_9〉
Liste complète des métadonnées

Littérature citée [10 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01402033
Contributeur : Hal Ifip <>
Soumis le : jeudi 24 novembre 2016 - 10:49:05
Dernière modification le : jeudi 24 novembre 2016 - 11:14:11
Document(s) archivé(s) le : mardi 21 mars 2017 - 03:35:01

Fichier

978-3-662-44602-7_9_Chapter.pd...
Fichiers produits par l'(les) auteur(s)

Licence


Distributed under a Creative Commons Paternité 4.0 International License

Identifiants

Citation

Hiroki Morizumi. Sensitivity, Block Sensitivity, and Certificate Complexity of Unate Functions and Read-Once Functions. Josep Diaz; Ivan Lanese; Davide Sangiorgi. 8th IFIP International Conference on Theoretical Computer Science (TCS), Sep 2014, Rome, Italy. Springer, Lecture Notes in Computer Science, LNCS-8705, pp.104-110, 2014, Theoretical Computer Science. 〈10.1007/978-3-662-44602-7_9〉. 〈hal-01402033〉

Partager

Métriques

Consultations de la notice

9

Téléchargements de fichiers

15