Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Paper:

TR05-020 | 22nd November 2004 00:00

#### On the Sensitivity of Cyclically-Invariant Boolean Functions

TR05-020
Authors: Sourav Chakraborty
Publication: 14th February 2005 10:30
Keywords:

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. Tur\'an (1984) asked if any
Boolean function, invariant under some transitive group of
permutations, has sensitivity $\Omega(\sqrt{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.

ISSN 1433-8092 | Imprint