Skip to content
DraconiticResearch
Search Sources API
203,203 studies31 sourcesUpdated 52 min ago
PreprintarXiv licencearXiv

Noise Sensitivity Governed by Continuous-Time Random Walks on the Symmetric Group

  • Gideon Amir
  • Subhajit Ghosh
Open at sourcePDFDOICite

Abstract

We study the noise sensitivity of Boolean functions on the symmetric group Sn, where noise is induced by running a continuous-time Markov chain on Sn. We investigate the noise sensitivity of several fundamental functions, including the parity function and analogues of the dictator function. We focus, in particular, on the case where the underlying Markov chain is an interchange process on the complete graph. We establish comparison results between noise sensitivity with respect to the interchange process on the complete graph and the weighted interchange process on any connected graph. We also show that the indicator function of long cycles is noise sensitive under the interchange process on each of these graphs. Finally, using the fact that the interchange process on the complete graph Kn is the continuous-time random walk generated by all transpositions, we prove that noise sensitivity is preserved when the noise source is changed to the continuous-time random walk generated by all s-cycles, where s is even and 2<s≪ n.

Related

  1. Sensitivity of Rotation Symmetric Boolean Functions via Binary Necklaces
    Yuan Li, Jing Zhang
    arXivPreprintCC0Full textCombinatorics & discrete mathematicsarXiv
  2. Stochastic heat equations with non-Lipschitz coefficients driven by symmetric α-stable Lévy white noise
    Juan J. Jiménez
    arXivPreprintCC BY 4.0Full textAnalysis & PDEsProbabilityarXiv
  3. Sensitivity and Block Sensitivity of Elementary Symmetric Boolean Functions of Arbitrary Degree
    Yuan Li, Jing Zhang
    arXivPreprintCC0Full textCombinatorics & discrete mathematicsarXiv
  4. Spatially Coupled MacKay-Neal Codes on Symmetric Markov Noise: A Reduction to BMS Channels
    Kenta Kasai
    arXivPreprintarXiv licenceFull textGeneral mathematicsarXiv
  5. Joint distributions of eigenvectors of symmetric random tensors
    Naoki Sasakura
    arXivPreprintCC BY 4.0Full textMathematical physicsHigh-energy & particle physicsarXiv

Cite

BibTeXRIS
BibTeX
@misc{amir2026noise,
  title = {{Noise Sensitivity Governed by Continuous-Time Random Walks on the Symmetric Group}},
  author = {Gideon Amir and Subhajit Ghosh},
  howpublished = {arXiv},
  year = {2026},
  month = oct,
  doi = {10.48550/arxiv.2606.29829},
  eprint = {2606.29829},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2606.29829},
}
RIS
TY  - UNPB
TI  - Noise Sensitivity Governed by Continuous-Time Random Walks on the Symmetric Group
AU  - Gideon Amir
AU  - Subhajit Ghosh
PY  - 2026
DA  - 2026/10/20
PB  - arXiv
DO  - 10.48550/arxiv.2606.29829
UR  - https://arxiv.org/abs/2606.29829
AB  - We study the noise sensitivity of Boolean functions on the symmetric group S_n, where noise is induced by running a continuous-time Markov chain on S_n. We investigate the noise sensitivity of several fundamental functions, including the parity function and analogues of the dictator function. We focus, in particular, on the case where the underlying Markov chain is an interchange process on the complete graph. We establish comparison results between noise sensitivity with respect to the interchange process on the complete graph and the weighted interchange process on any connected graph. We also show that the indicator function of long cycles is noise sensitive under the interchange process on each of these graphs. Finally, using the fact that the interchange process on the complete graph K_n is the continuous-time random walk generated by all transpositions, we prove that noise sensitivity is preserved when the noise source is changed to the continuous-time random walk generated by all s-cycles, where s is even and 2<s≪ n.
ER  -