@inproceedings{bf6a1e85e3304b01a2abfd13f6dbb6be,

title = "On polynomial representations of boolean functions related to some number theoretic problems",

abstract = "We say a polynomial P over ZM strongly M-represents a Boolean function F if F(x) ≡ P(x) (mod M) for all x ∈ {0, 1}n. Similarly, P one-sidedly M-represents F if F(x) = 0 ⇐⇒ P(x) ≡ 0 (mod M) for all x ∈ {0, 1}n. Lower bounds are obtained on the degree and the number of monomials of polynomials over ZM, which strongly or one-sidedly M-represent the Boolean function deciding if a given nbit integer is square-free. Similar lower bounds are also obtained for polynomials over the reals which provide a threshold representation of the above Boolean function.",

author = "Erion Plaku and Shparlinski, {Igor E.}",

year = "2001",

month = dec,

doi = "10.1007/3-540-45294-X_26",

language = "English",

isbn = "3540430024",

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

publisher = "Springer, Springer Nature",

pages = "305--316",

editor = "Ramesh Hariharan and V. Vinay and Madhavan Mukund",

booktitle = "FST TCS 2001: Foundations of Software Technology and Theoretical Computer Science",

address = "United States",

note = "21st Conference on Foundations of Software Technology and Theoretical Computer Science, FST TCS - 2001 ; Conference date: 13-12-2001 Through 15-12-2001",

}