| 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. | |||||||||||||
Publication details | |||||||||||||
| |||||||||||||