Circuit and decision tree complexity of some number theoretic problems

Authors
Bernasconi, A Damm, C Shparlinski, I
Citation
A. Bernasconi et al., Circuit and decision tree complexity of some number theoretic problems, INF COMPUT, 168(2), 2001, pp. 113-124
Citations number
29
Categorie Soggetti
Information Tecnology & Communication Systems
Journal title
INFORMATION AND COMPUTATION
ISSN journal
08905401 → ACNP
Volume
168
Issue
2
Year of publication
2001
Pages
113 - 124
Database
ISI
SICI code
0890-5401(20010801)168:2<113:CADTCO>2.0.ZU;2-U
Abstract
We extend the area of applications of the Abstract Harmonic Analysis to low er bounds on the circuit and decision tree complexity of Boolean functions related to some number theoretic problems. In particular, we prove that dec iding if a given integer is square-free and testing co-primality of two int egers by unbounded fan-in circuits of bounded depth requires super-polynomi al size. (C) 2001 Academic Press.