Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR98-054 | 26th August 1998 00:00

On Polynomial Representations of Boolean Functions Related to Some Number Theoretic Problems

RSS-Feed




TR98-054
Authors: Igor E. Shparlinski
Publication: 6th September 1998 22:24
Downloads: 3395
Keywords: 


Abstract:

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.




ISSN 1433-8092 | Imprint