| On the Complexity of Some Arithmetic Problems over IF2[T] (2007) | |||||||||||||||
Abstract | |||||||||||||||
| In this paper, we study various combinatorial complexity characteristics of Boolean functions related to some natural arithmetic problems about polynomials over IF2. In particular, we consider the Boolean function deciding whether a given polynomial over IF2 is squarefree. We obtain an exponential lower bound on the size of a decision tree for this function, and derive an asymptotic formula, having a linear main term, for its average sensitivity. This allows us to estimate other complexity characteristics such as the formula size, the average decision tree depth and the degrees of exact and approximative polynomial representations of this function. Finally, using a different method, we show that squarefree testing and deciding irreducibility of polynomials over IF2 are not in AC 0 [p] for any odd prime p. Similar results are obtained for deciding co-primality of two polynomials over IF2 as well. 2 1 | |||||||||||||||
Publication details | |||||||||||||||
| |||||||||||||||