Reconstruction des circuits arithmétiques génériques de profondeur constante.


Jules Armand, LIMD. 30 janvier 2025 10:00 TLR limd 2:00:00
Abstract:

Les circuits arithmétiques sont un modèle de calcul des polynômes multivariés sur un corps $\mathbb{K}$. Des problèmes classiques difficiles sur les circuits sont notamment les questions de calcul de bornes inférieures (quelle est la taille minimale d'un circuit calculant un certain polynôme), de test d'identité (donné un circuit, quelle est la complexité de tester si ce circuit calcule le polynôme identiquement nul) ou de reconstruction (Étant donné un accès oracle à un polynôme $f$ calculé par un certain circuit $C$, peut-on reconstruire un circuit similaire $C'$ calculant $f$). On se penchera sur le dernier problème. La question de la reconstruction est ouverte dans le cas général mais il existe des méthodes de reconstruction pour certaines classes de circuits et notamment pour des sous-familles de profondeur constante.