Skip to Main content Skip to Navigation
Journal articles

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

Cited literature [8 references]  Display  Hide  Download
Contributor : Service Ist Inria Sophia Antipolis-Méditerranée / I3s Connect in order to contact the contributor
Submitted on : Tuesday, May 13, 2014 - 3:39:26 PM
Last modification on : Thursday, September 7, 2017 - 1:03:38 AM
Long-term archiving on: : Monday, April 10, 2017 - 10:19:36 PM


Files produced by the author(s)




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. ⟨10.46298/dmtcs.552⟩. ⟨hal-00990492⟩



Record views


Files downloads