Sourav Chakraborty - On the sensitivity of cyclically-invariant Boolean functions

dmtcs:552 - Discrete Mathematics & Theoretical Computer Science, December 4, 2011, Vol. 13 no. 4 -
On the sensitivity of cyclically-invariant Boolean functionsArticle

Authors: Sourav Chakraborty 1

  • 1 Chennai Mathematical Institute [Inde]

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.

Volume: Vol. 13 no. 4
Published on: December 4, 2011
Accepted on: June 9, 2015
Submitted on: June 29, 2010
Keywords: [INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM]

9 Documents citing this article

Consultation statistics

This page has been seen 357 times.
This article's PDF has been downloaded 259 times.