期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：1998
卷号：1998
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：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.
关键词：circuit complexity, Class ACo, Testing Square-Free Numbers
