Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR05-020 | 22nd November 2004 00:00

On the Sensitivity of Cyclically-Invariant Boolean Functions

RSS-Feed




TR05-020
Authors: Sourav Chakraborty
Publication: 14th February 2005 10:30
Downloads: 895
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