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 univariate polynomials of the form $\sum_{j=0}^t c_j X^{\alpha_j} (a + b X)^{\beta_j}$. From our algorithm we derive an exponential lower bound for representations of polynomials such as $\prod_{i=1}^{2^n} (X^i-1)$ under this form. It has been conjectured that these polynomials are hard to compute by general arithmetic circuits. Our result shows that the ``hardness from derandomization'' approach to lower bounds is feasible for a restricted class of arithmetic circuits. The proof is based on techniques from algebraic number theory, and more precisely on properties of the height function of algebraic numbers.
Document type :
Preprints, Working Papers, ...
Complete list of metadatas

Cited literature [23 references]  Display  Hide  Download

https://hal-ens-lyon.archives-ouvertes.fr/ensl-00408713
Contributor : Pascal Koiran <>
Submitted on : Monday, December 7, 2009 - 11:01:27 PM
Last modification on : Thursday, November 21, 2019 - 2:32:57 AM
Long-term archiving on : Thursday, September 23, 2010 - 11:17:26 AM

Files

fields.pdf
Files produced by the author(s)

Identifiers

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

Collections

Citation

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

Share

Metrics

Record views

112

Files downloads

111