| A hitting set construction, with application to arithmetic circuit lower bounds (2009) | |||||||||
Abstract | |||||||||
| 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.. Comment: 13 pages | |||||||||
Publication details | |||||||||
| |||||||||