On the average sensitivity of testing square-free numbers

Anna Bernasconi; Carsten Damm; Igor E. Shparlinski

doi:10.1007/3-540-48686-0_29

On the average sensitivity of testing square-free numbers

Anna Bernasconi, Carsten Damm, Igor E. Shparlinski

School of Computing

Research output: Chapter in Book/Report/Conference proceeding › Conference proceeding contribution › peer-review

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 language	English
Title of host publication	Computing and Combinatorics - 5th Annual International Conference, COCOON 1999, Proceedings
Editors	Takao Asano, Hideki Imai, D. T. Lee, Shin-ichi Nakano, Takeshi Tokuyama
Place of Publication	Berlin ; Heidelberg ; New York
Publisher	Springer, Springer Nature
Pages	291-299
Number of pages	9
Volume	1627
ISBN (Print)	3540662006, 9783540662006
DOIs	https://doi.org/10.1007/3-540-48686-0_29
Publication status	Published - 1999
Event	5th Annual International Conference on Computing and Combinatorics, COCOON - 1999 - Tokyo, Japan Duration: 26 Jul 1999 → 28 Jul 1999

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	1627
ISSN (Print)	03029743
ISSN (Electronic)	16113349

Other

Other	5th Annual International Conference on Computing and Combinatorics, COCOON - 1999
Country/Territory	Japan
City	Tokyo
Period	26/07/99 → 28/07/99

Access to Document

10.1007/3-540-48686-0_29

Cite this

Bernasconi, A., Damm, C., & Shparlinski, I. E. (1999). On the average sensitivity of testing square-free numbers. In T. Asano, H. Imai, D. T. Lee, S. Nakano, & T. Tokuyama (Eds.), Computing and Combinatorics - 5th Annual International Conference, COCOON 1999, Proceedings (Vol. 1627, pp. 291-299). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 1627). Springer, Springer Nature. https://doi.org/10.1007/3-540-48686-0_29

Bernasconi, Anna ; Damm, Carsten ; Shparlinski, Igor E. / On the average sensitivity of testing square-free numbers. Computing and Combinatorics - 5th Annual International Conference, COCOON 1999, Proceedings. editor / Takao Asano ; Hideki Imai ; D. T. Lee ; Shin-ichi Nakano ; Takeshi Tokuyama. Vol. 1627 Berlin ; Heidelberg ; New York : Springer, Springer Nature, 1999. pp. 291-299 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

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

}

Bernasconi, A, Damm, C & Shparlinski, IE 1999, On the average sensitivity of testing square-free numbers. in T Asano, H Imai, DT Lee, S Nakano & T Tokuyama (eds), Computing and Combinatorics - 5th Annual International Conference, COCOON 1999, Proceedings. vol. 1627, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 1627, Springer, Springer Nature, Berlin ; Heidelberg ; New York, pp. 291-299, 5th Annual International Conference on Computing and Combinatorics, COCOON - 1999, Tokyo, Japan, 26/07/99. https://doi.org/10.1007/3-540-48686-0_29

On the average sensitivity of testing square-free numbers. / Bernasconi, Anna; Damm, Carsten; Shparlinski, Igor E.
Computing and Combinatorics - 5th Annual International Conference, COCOON 1999, Proceedings. ed. / Takao Asano; Hideki Imai; D. T. Lee; Shin-ichi Nakano; Takeshi Tokuyama. Vol. 1627 Berlin ; Heidelberg ; New York: Springer, Springer Nature, 1999. p. 291-299 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 1627).

Research output: Chapter in Book/Report/Conference proceeding › Conference proceeding contribution › peer-review

TY - GEN

T1 - On the average sensitivity of testing square-free numbers

AU - Bernasconi, Anna

AU - Damm, Carsten

AU - Shparlinski, Igor E.

PY - 1999

Y1 - 1999

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=84957796979&partnerID=8YFLogxK

U2 - 10.1007/3-540-48686-0_29

DO - 10.1007/3-540-48686-0_29

M3 - Conference proceeding contribution

AN - SCOPUS:84957796979

SN - 3540662006

SN - 9783540662006

VL - 1627

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 291

EP - 299

BT - Computing and Combinatorics - 5th Annual International Conference, COCOON 1999, Proceedings

A2 - Asano, Takao

A2 - Imai, Hideki

A2 - Lee, D. T.

A2 - Nakano, Shin-ichi

A2 - Tokuyama, Takeshi

PB - Springer, Springer Nature

CY - Berlin ; Heidelberg ; New York

T2 - 5th Annual International Conference on Computing and Combinatorics, COCOON - 1999

Y2 - 26 July 1999 through 28 July 1999

ER -

Bernasconi A, Damm C, Shparlinski IE. On the average sensitivity of testing square-free numbers. In Asano T, Imai H, Lee DT, Nakano S, Tokuyama T, editors, Computing and Combinatorics - 5th Annual International Conference, COCOON 1999, Proceedings. Vol. 1627. Berlin ; Heidelberg ; New York: Springer, Springer Nature. 1999. p. 291-299. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/3-540-48686-0_29

On the average sensitivity of testing square-free numbers

Abstract

Publication series

Other

Access to Document

Other files and links

Fingerprint

Cite this