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 language | English |
|---|---|
| Pages (from-to) | 113-124 |
| Number of pages | 12 |
| Journal | Information and Computation |
| Volume | 168 |
| Issue number | 2 |
| DOIs | |
| Publication status | Published - 1 Aug 2001 |