TY - JOUR
T1 - Complexity of some arithmetic problems for binary polynomials
AU - Allender, Eric
AU - Bernasconi, Anna
AU - Damm, Carsten
AU - Von Zur Gathen, Joachim
AU - Saks, Michael
AU - Shparlinski, Igor
PY - 2003
Y1 - 2003
N2 - We study various combinatorial complexity measures of Boolean functions related to some natural arithmetic problems about binary polynomials, that is, polynomials over Struct F sign 2. In particular, we consider the Boolean function deciding whether a given polynomial over Struct F sign 2 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 testing squarefreeness and irreducibility of polynomials over Struct F sign2 cannot be done in AC0[p] for any odd prime p. Similar results are obtained for deciding coprimality of two polynomials over Struct F sign 2 as well.
AB - We study various combinatorial complexity measures of Boolean functions related to some natural arithmetic problems about binary polynomials, that is, polynomials over Struct F sign 2. In particular, we consider the Boolean function deciding whether a given polynomial over Struct F sign 2 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 testing squarefreeness and irreducibility of polynomials over Struct F sign2 cannot be done in AC0[p] for any odd prime p. Similar results are obtained for deciding coprimality of two polynomials over Struct F sign 2 as well.
UR - http://www.scopus.com/inward/record.url?scp=2442709148&partnerID=8YFLogxK
M3 - Article
VL - 12
SP - 23
EP - 47
JO - Computational Complexity
JF - Computational Complexity
SN - 1016-3328
IS - 1-2
ER -