ECCC-Report TR05-020https://eccc.weizmann.ac.il/report/2005/020Comments and Revisions published for TR05-020en-usMon, 14 Feb 2005 10:30:05 +0200
Paper TR05-020
| On the Sensitivity of Cyclically-Invariant Boolean Functions |
Sourav Chakraborty
https://eccc.weizmann.ac.il/report/2005/020In 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.
Mon, 14 Feb 2005 10:30:05 +0200https://eccc.weizmann.ac.il/report/2005/020