On the sensitivity of cyclically-invariant Boolean functions

Abstract : In this paper we construct a cyclically invariant Boolean function whose sensitivity is Theta(n(1/3)). This result answers two previously published questions. Turan (1984) asked if any Boolean function, invariant under some transitive group of permutations, has sensitivity Omega(root n). Kenyon and Kutin (2004) asked whether for a "nice" function the product of 0-sensitivity and 1-sensitivity is Omega(n). Our function answers both questions in the negative. We also prove that for minterm-transitive functions (a natural class of Boolean functions including our example) the sensitivity is Omega(n(1/3)). Hence for this class of functions sensitivity and block sensitivity are polynomially related.
Type de document :
Article dans une revue
Discrete Mathematics and Theoretical Computer Science, DMTCS, 2011, Vol. 13 no. 4 (4), pp.51--60
Liste complète des métadonnées

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

https://hal.inria.fr/hal-00990492
Contributeur : Service Ist Inria Sophia Antipolis-Méditerranée / I3s <>
Soumis le : mardi 13 mai 2014 - 15:39:26
Dernière modification le : jeudi 7 septembre 2017 - 01:03:38
Document(s) archivé(s) le : lundi 10 avril 2017 - 22:19:36

Fichier

2050-6590-2-PB.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-00990492, version 1

Collections

Citation

Sourav Chakraborty. On the sensitivity of cyclically-invariant Boolean functions. Discrete Mathematics and Theoretical Computer Science, DMTCS, 2011, Vol. 13 no. 4 (4), pp.51--60. 〈hal-00990492〉

Partager

Métriques

Consultations de la notice

56

Téléchargements de fichiers

724