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-056 | 31st August 1998 00:00

Circuit Complexity of Testing Square-Free Numbers

RSS-Feed




TR98-056
Authors: Anna Bernasconi, Igor E. Shparlinski
Publication: 7th September 1998 16:54
Downloads: 1096
Keywords: 


Abstract:

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 allows us to prove that testing square-free numbers by
unbounded fan-in circuits of bounded depth requires a superpolynomial size.
This implies the same estimate for the integer factorization problem.



ISSN 1433-8092 | Imprint