Skip to main contentSkip to search
Episciences
Open Access Journals
Sign in(new window)
Discrete Mathematics & Theoretical Computer Science logo
Discrete Mathematics & Theoretical Computer Science
Discrete Mathematics & Theoretical Computer Science logo
Discrete Mathematics & Theoretical Computer Science
Sign in(new window)
Articles & Issues
All articlesAll accepted articlesAll volumesLast volumeSectionsSpecial issuesAuthors
About
The journalIndexing
Boards
Publish
For authorsEthical charter
Submit
Discrete Mathematics & Theoretical Computer Science logo
Contact
|
Credits
eISSN 1365-8050
|
RSS
|
Atom
Episciences
Documentation
|
Acknowledgements
|
Publishing policy
Accessibility: non-compliant
|
Legal mentions
|
Privacy statement
|
Terms of use
  1. Home > Articles & Issues >
  2. Articles >
  3. On the sensitivity o ...
Article

On the sensitivity of cyclically-invariant Boolean functions

Sourav Chakraborty (1)
(1) Chennai Mathematical Institute [Inde]
Download article
Open on HAL
Imported on
June 28, 2010
Published on
December 3, 2011
Last modified on
March 31, 2025
Volume 13
vol. 13:4, Special Issue in honor of Laci Babai's 60th birthday: Combinatorics, Groups, Algorithms, and Complexity
DOI
10.46298/dmtcs.552
License
https://about.hal.science/hal-authorisation-v1
Indicators
762
Views
750
Downloads

On the sensitivity of cyclically-invariant Boolean functions

Sourav Chakraborty (1)
(1) Chennai Mathematical Institute [Inde]
Abstract
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.
Keywords
  • [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM]
Cited by

Source: OpenCitations

  • Gems in decision tree complexity revisited

    ACM SIGACT News

    Authors : Raghav Kulkarni

    Journal reference : Volume 44, 2013, pp. 42-55

    DOI : 10.1145/2527748.2527763

  • Minterm-transitive functions with asymptotically smallest block sensitivity

    Information Processing Letters

    Authors : Kazuyuki Amano ORCID

    Journal reference : Volume 111, 2011, pp. 1081-1084

    DOI : 10.1016/j.ipl.2011.09.008

  • On the Sensitivity Complexity of k -Uniform Hypergraph Properties

    ACM Transactions on Computation Theory

    Authors : Qian Li ORCID, Xiaoming Sun ORCID

    Journal reference : Volume 13, 2021, pp. 1-13

    DOI : 10.1145/3448643

  • Robustness and stability of spin-glass ground states to perturbed interactions

    Physical review. E

    Authors : Vaibhav Mohanty ORCID, Ard A. Louis ORCID

    Journal reference : Volume 107, 2023, pp. 014126

    DOI : 10.1103/physreve.107.014126

  • Separations between Combinatorial Measures for Transitive Functions

    Discrete Mathematics & Theoretical Computer Science

    Authors : Sourav Chakraborty ORCID, Chandrima Kayal, Manaswi Paraashar ORCID

    Journal reference : Volume vol. 27:2, 2025, pp.

    DOI : 10.46298/dmtcs.11133

  • Block sensitivity of minterm-transitive functions

    Edinburgh Research Explorer (University of Edinburgh)

    Authors : Andrew Drucker

    Journal reference : Volume 412, 2011, pp. 5796-5801

    DOI : 10.1016/j.tcs.2011.06.025

  • A Tighter Relation Between Sensitivity Complexity and Certificate Complexity

    Lecture notes in computer science

    Authors : Kun He ORCID, Qian Li ORCID, Xiaoming Sun ORCID

    Journal reference : Volume , 2017, pp. 262-274

    DOI : 10.1007/978-3-319-62389-4_22

  • Block sensitivity of weakly symmetric functions

    Theoretical Computer Science

    Authors : Xiaoming Sun

    Journal reference : Volume 384, 2007, pp. 87-91

    DOI : 10.1016/j.tcs.2007.05.020

  • On the Sensitivity Conjecture for Read-k Formulas

    DROPS (Schloss Dagstuhl – Leibniz Center for Informatics)

    Authors : Bafna, Lokam, Tavenas, Velingker

    Journal reference : Volume , 2016, pp.

    DOI : 10.4230/lipics.mfcs.2016.16

  • Block Sensitivity of Weakly Symmetric Functions

    Lecture notes in computer science

    Authors : Xiaoming Sun ORCID

    Journal reference : Volume , 2006, pp. 339-344

    DOI : 10.1007/11750321_32

  • An improved lower bound on the sensitivity complexity of graph properties

    Theoretical Computer Science

    Authors : Xiaoming Sun ORCID

    Journal reference : Volume 412, 2011, pp. 3524-3529

    DOI : 10.1016/j.tcs.2011.02.042

  • Alternation, sparsity and sensitivity: Bounds and exponential gaps

    Theoretical Computer Science

    Authors : Krishnamoorthy Dinesh ORCID, Jayalal Sarma

    Journal reference : Volume 771, 2018, pp. 71-82

    DOI : 10.1016/j.tcs.2018.11.015
Preview
Loading PDF preview...