Discrete Mathematics & Theoretical Computer Science, Vol 13, No 4

Font Size:  Small  Medium  Large

On the sensitivity of cyclically-invariant Boolean functions

Sourav Chakraborty


In this paper we construct a cyclically invariant Boolean function whose sensitivity is Θ(n1/3). This result answers two previously published questions. Turán (1984) asked if any Boolean function, invariant under some transitive group of permutations, has sensitivity Ω(n). Kenyon and Kutin (2004) asked whether for a ``nice'' function the product of 0-sensitivity and 1-sensitivity is Ω(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 Ω(n1/3). Hence for this class of functions sensitivity and block sensitivity are polynomially related.

Full Text: PDF PostScript