Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with Testing Square-Free Numbers:
TR98-054 | 26th August 1998
Igor E. Shparlinski

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

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
more >>>

TR98-056 | 31st August 1998
Anna Bernasconi, Igor E. Shparlinski

Circuit Complexity of Testing Square-Free Numbers

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 ... more >>>

ISSN 1433-8092 | Imprint