On the sensitivity of cyclically-invariant Boolean functions
Sourav Chakraborty
Abstract
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