On the average sensitivity of testing square-free numbers

Anna Bernasconi, Carsten Damm, Igor E. Shparlinski

Research output: Chapter in Book/Report/Conference proceedingConference proceeding contribution

8 Citations (Scopus)

Abstract

We study combinatorial complexity characteristics of a Boolean function related to a natural number theoretic problem. In par- ticular we obtain a linear lower bound on 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 approximative polynomial representations of this function.

Original languageEnglish
Title of host publicationComputing and Combinatorics - 5th Annual International Conference, COCOON 1999, Proceedings
EditorsTakao Asano, Hideki Imai, D. T. Lee, Shin-ichi Nakano, Takeshi Tokuyama
Place of PublicationBerlin ; Heidelberg ; New York
PublisherSpringer, Springer Nature
Pages291-299
Number of pages9
Volume1627
ISBN (Print)3540662006, 9783540662006
DOIs
Publication statusPublished - 1999
Event5th Annual International Conference on Computing and Combinatorics, COCOON - 1999 - Tokyo, Japan
Duration: 26 Jul 199928 Jul 1999

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume1627
ISSN (Print)03029743
ISSN (Electronic)16113349

Other

Other5th Annual International Conference on Computing and Combinatorics, COCOON - 1999
CountryJapan
CityTokyo
Period26/07/9928/07/99

Fingerprint Dive into the research topics of 'On the average sensitivity of testing square-free numbers'. Together they form a unique fingerprint.

Cite this