Bernard Chazelle, \'Ecole polytechnique et Inria

Bornes inf\'erieures pour circuits arithm\'etiques. Premi\`ere partie (Expos\'e en 2 parties).

On consid\`ere la complexit\'e arithm\'etique de la fonction $x \mapsto Ax$, o\`u $A$ est la matrice d'incidence d'une famille d'ensembles g\'eom\'etriques. On \'etablit des bornes inf\'erieures pour les circuits non monotones en bornant les valeurs propres de la matrice $A^TA$. Pour ce faire on est amen\'e \`a adapter des techniques de fonctions orthogonales inspir\'ees de la th\'eorie de la discr\'epance. Note : Ces r\'esultats font application du ``Lemme Spectral''. La preuve du lemme n'est pas essentielle \`a la compr\'ehension de l'expos\'e (cf. conf\'erence du 28 Janvier \`a l'ENS).