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.
Type de document :
Pré-publication, Document de travail
14 pages. 2009
Liste complète des métadonnées

Littérature citée [23 références]  Voir  Masquer  Télécharger

https://hal-ens-lyon.archives-ouvertes.fr/ensl-00408713
Contributeur : Pascal Koiran <>
Soumis le : lundi 7 décembre 2009 - 23:01:27
Dernière modification le : mardi 24 avril 2018 - 13:52:38
Document(s) archivé(s) le : jeudi 23 septembre 2010 - 11:17:26

Fichiers

fields.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

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

Collections

Citation

Pascal Koiran. A hitting set construction, with application to arithmetic circuit lower bounds. 14 pages. 2009. 〈ensl-00408713v2〉

Partager

Métriques

Consultations de la notice

101

Téléchargements de fichiers

91