On the sensitivity of cyclically-invariant Boolean functions

Sourav Chakraborty

doi:10.46298/dmtcs.552

Sourav Chakraborty - On the sensitivity of cyclically-invariant Boolean functions

dmtcs:552 - Discrete Mathematics & Theoretical Computer Science, December 4, 2011, Vol. 13 no. 4 - https://doi.org/10.46298/dmtcs.552

On the sensitivity of cyclically-invariant Boolean functionsArticle

Authors: Sourav Chakraborty ¹

1 Chennai Mathematical Institute [Inde]

special issue in honor of Laci Babai's 60th birthday: Combinatorics, Groups, Algorithms, and Complexity

[en]
In this paper we construct a cyclically invariant Boolean function whose sensitivity is Theta(n(1/3)). This result answers two previously published questions. Turan (1984) asked if any Boolean function, invariant under some transitive group of permutations, has sensitivity Omega(root 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.

https://doi.org/10.46298/dmtcs.552

Source: HAL:hal-00990492v1

Volume: Vol. 13 no. 4

Published on: December 4, 2011

Imported on: June 29, 2010

Keywords: [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM]

Bibliographic References

11 Documents citing this article

Vaibhav Mohanty;Ard A. Louis, 2023, Robustness and stability of spin-glass ground states to perturbed interactions, Physical review. E, 107, 1, pp. 014126, 10.1103/physreve.107.014126.

Qian Li;Xiaoming Sun, 2021, On the Sensitivity Complexity of k -Uniform Hypergraph Properties, ACM Transactions on Computation Theory, 13, 2, pp. 1-13, 10.1145/3448643.

Krishnamoorthy Dinesh;Jayalal Sarma, 2018, Alternation, sparsity and sensitivity: Bounds and exponential gaps, arXiv (Cornell University), 771, pp. 71-82, 10.1016/j.tcs.2018.11.015, http://arxiv.org/abs/1712.05735.

Kun He;Qian Li;Xiaoming Sun, 2017, A Tighter Relation Between Sensitivity Complexity and Certificate Complexity, Lecture notes in computer science, pp. 262-274, 10.1007/978-3-319-62389-4_22.

Mitali Bafna;Satyanarayana V. Lokam;Sébastien Tavenas;Ameya Velingker, 2016, On the Sensitivity Conjecture for Read-k Formulas, Leibniz-Zentrum für Informatik (Schloss Dagstuhl), 10.4230/lipics.mfcs.2016.16, https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2016.16.

Raghav Kulkarni, 2013, Gems in decision tree complexity revisited, ACM SIGACT News, 44, 3, pp. 42-55, 10.1145/2527748.2527763.

Andrew Drucker, 2011, Block sensitivity of minterm-transitive functions, Theoretical Computer Science, 412, 41, pp. 5796-5801, 10.1016/j.tcs.2011.06.025.

Kazuyuki Amano, 2011, Minterm-transitive functions with asymptotically smallest block sensitivity, Information Processing Letters, 111, 23-24, pp. 1081-1084, 10.1016/j.ipl.2011.09.008.

Xiaoming Sun, 2011, An improved lower bound on the sensitivity complexity of graph properties, Theoretical Computer Science, 412, 29, pp. 3524-3529, 10.1016/j.tcs.2011.02.042.

Xiaoining Sun, 2007, Block sensitivity of weakly symmetric functions, Theoretical Computer Science, 384, 1, pp. 87-91, 10.1016/j.tcs.2007.05.020.

Xiaoming Sun, 2006, Block Sensitivity of Weakly Symmetric Functions, Lecture notes in computer science, pp. 339-344, 10.1007/11750321_32.

Sources : OpenCitations, OpenAlex & Crossref

Share and export

Consultation statistics

This page has been seen 494 times.

This article's PDF has been downloaded 506 times.