The average sensitivity of square-freeness
2000 | journal article. A publication with affiliation to the University of Göttingen.
Jump to: Cite & Linked | Documents & Media | Details | Version history
Documents & Media
Details
- Authors
- Bernasconi, A.; Damm, C. ; Shparlinski, I.
- 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.
- Issue Date
- 2000
- Journal
- Computational Complexity
- ISSN
- 1016-3328
- Language
- English