@inproceedings{da3a071d1e5a454faaa2b5d338a34392,

title = "Circuit complexity of testing square-free numbers",

abstract = "In this paper we extend the area of applications of the Abstract Harmonic Analysis to the field of Boolean function complexity. In particular, we extend the class of functions to which a spectral technique developed in a series of works of the first author can be applied. This extension allows us to prove that testing square-free numbers by unbounded fan-in circuits of bounded depth requires a superpolynomial size. This implies the same estimate for the integer factorization problem.",

author = "Anna Bernasconi and Igor Shparlinski",

year = "1999",

language = "English",

isbn = "354065691X",

volume = "1563",

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

publisher = "Springer, Springer Nature",

pages = "47--56",

editor = "Christoph Meinel and Sophie Tison",

booktitle = "STACS 99",

address = "United States",

note = "16th Annual Symposium on Theoretical Aspects of Computer Science, STACS 1999 ; Conference date: 04-03-1999 Through 06-03-1999",

}