For a permutation group $G$ acting on the set $\Omega$ we say that two strings $x,y\,:\,\Omega\to\boole$ are {\em $G$-isomorphic} if they are equivalent under the action of $G$, \ie, if for some $\pi\in G$ we have $x(i^{\pi})=y(i)$ for all $i\in\Omega$. Cyclic Shift, Graph Isomorphism and Hypergraph Isomorphism are special cases, ... more >>>

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 ... more >>>