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

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.
Keywords :
Document type :
Preprints, Working Papers, ...

https://hal-ens-lyon.archives-ouvertes.fr/ensl-00408713
Contributor : Pascal Koiran Connect in order to contact the contributor
Submitted on : Friday, July 31, 2009 - 6:47:17 PM
Last modification on : Friday, September 10, 2021 - 2:34:03 PM
Long-term archiving on: : Tuesday, June 15, 2010 - 8:25:22 PM

Files

prunel.pdf
Files produced by the author(s)

Identifiers

• HAL Id : ensl-00408713, version 1
• ARXIV : 0907.5575

Citation

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

Record views