Circuit and decision tree complexity of some number theoretic problems

Anna Bernasconi*, Carsten Damm, Igor Shparlinski

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

9 Citations (Scopus)

Abstract

Circuit and decision tree complexity of some number theoretic problems are discussed. The area of application of the Abstract Harmonic Analysis are extended to lower bounds on the circuit and decision tree complexity of Boolean functions related to some number theoretic problems. It is proved that superpolynomial size was required to decide if a given integer is square-free testing co-primality of two integers.

Original languageEnglish
Pages (from-to)113-124
Number of pages12
JournalInformation and Computation
Volume168
Issue number2
DOIs
Publication statusPublished - 1 Aug 2001

Fingerprint Dive into the research topics of 'Circuit and decision tree complexity of some number theoretic problems'. Together they form a unique fingerprint.

Cite this