In this talk, we focus on the Boolean functions on the symmetric group. The noise sources are various continuous-time random walks on the symmetric group. First, we focus on the continuous-time random transposition walk, and state equivalent criterion for noise sensitivity and noise stability. These involve the Fourier transformation of the given function at irreducible representations (of the symmetric group). We use them to study the sensitivity/stability nature of some Boolean functions, viz., the parity function, the dictator function, and the indicator of the set of permutations with ``long" cycles. Finally, we give some comparison results when the noise source is other continuous-time random walks, viz. the star transposition, $s$-cycles ($s$ is even and ``small enough"). The techniques used in this talk are based on the representation theory of the symmetric group. This is based on an ongoing work in progress with Gideon Amir.
Noise Sensitivity Governed by Random Walks on the Symmetric Group
Abstract: