@inproceedings{baac6ac1a6094f6192aab86bf8cabad8,

title = "On the average sensitivity of testing square-free numbers",

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.",

author = "Anna Bernasconi and Carsten Damm and Shparlinski, {Igor E.}",

year = "1999",

doi = "10.1007/3-540-48686-0_29",

language = "English",

isbn = "3540662006",

volume = "1627",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer, Springer Nature",

pages = "291--299",

editor = "Takao Asano and Hideki Imai and Lee, {D. T.} and Shin-ichi Nakano and Takeshi Tokuyama",

booktitle = "Computing and Combinatorics - 5th Annual International Conference, COCOON 1999, Proceedings",

address = "United States",

note = "5th Annual International Conference on Computing and Combinatorics, COCOON - 1999 ; Conference date: 26-07-1999 Through 28-07-1999",

}