期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：1998
卷号：1998
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：Lower bounds are obtained on the degree and the number of monomials of
Boolean functions, considered as a polynomial over GF(2),
which decide if a given r-bit integer is square-free.
Similar lower bounds are also obtained for polynomials
over the reals which provide a threshold representation
of the above Boolean functions. These results provide first non-trivial lower bounds on
the complexity of a number theoretic
problem which is closely related to the integer factorization problem.
