The average sensitivity of square-freeness

Anna Bernasconi*, Carsten Damm, Igor Shparlinski

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

9 Citations (Scopus)

Abstract

We study combinatorial complexity characteristics of a Boolean function related to a natural number theoretic problem. In particular we obtain an asymptotic formula, having a linear main term, for the average sensitivity of the Boolean function deciding whether a given integer is square-free. This result allows us to derive a quadratic lower bound for the formula size complexity of testing square-free numbers and a linear lower bound on the average decision tree depth. We also obtain lower bounds on the degrees of exact and approximate polynomial representations of this function.

Original languageEnglish
Pages (from-to)39-51
Number of pages13
JournalComputational Complexity
Volume9
Issue number1
Publication statusPublished - 2000

Keywords

  • Average sensitivity
  • Combinatorial complexity
  • Square-freeness

Fingerprint Dive into the research topics of 'The average sensitivity of square-freeness'. Together they form a unique fingerprint.

Cite this