A hitting set construction, with application to arithmetic circuit lower bounds

Pascal Koiran (1)

1 LIP - Laboratoire de l'Informatique du Parallélisme

A polynomial identity testing algorithm must determine whether a given input polynomial is identically equal to 0. We give a deterministic black-box identity testing algorithm for polynomials of the form $\sum_{j=0}^t c_j X^{\alpha_j} (a + b X)^{\beta_j}$, and from there we derive a lower bound for representations of univariate polynomials under this form. This shows that the ``hardness from derandomization'' approach to lower bounds is feasible for a restricted class of arithmetic circuits.

Mots clés: computational complexity; arithmetic circuits; polynomial identity testing; derandomization; hitting sets; lower bounds; height of algebraic numbers

Domaines: Complexité [cs.CC]

Pascal Koiran. A hitting set construction, with application to arithmetic circuit lower bounds. 2009. ⟨ensl-00408713v1⟩