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