Bounds on an exponential sum arising in Boolean circuit complexity - 01/01/05
Bienvenue sur EM-consulte, la référence des professionnels de santé.
L’accès au texte intégral de cet article nécessite un abonnement.
| pages | 4 |
| Iconographies | 0 |
| Vidéos | 0 |
| Autres | 0 |
Abstract |
We study exponential sums of the form 
, where 
are relatively prime, p is a polynomial with coefficients in 
, and 
for some 
. We prove an upper bound of the form 
on 
. This generalizes a result of J. Bourgain, who establishes this bound in the case where q is odd. This bound has consequences in Boolean circuit complexity. To cite this article: F. Green et al., C. R. Acad. Sci. Paris, Ser. I 341 (2005).
Résumé |
On étudie les sommes exponentielles de la forme 
, où 
sont des entiers premiers entre eux, p est un polynôme à coefficients dans 
et 
, avec 
. On démontre que 
. Ceci généralise un résultat de J. Bourgain, qui établit cette borne dans le cas où q est impair. Ce théorème a des conséquences dans lʼétude de la complexité des circuits booléens. Pour citer cet article : F. Green et al., C. R. Acad. Sci. Paris, Ser. I 341 (2005).
Plan
Vol 341 - N° 5
P. 279-282 - septembre 2005 Retour au numéro
Article précédent
- Un analogue elliptique du théorème de Roth
- Bakir Farhi
- Schur finiteness and nilpotency
- Alessio Del Padrone, Carlo Mazza
Bienvenue sur EM-consulte, la référence des professionnels de santé.
L’accès au texte intégral de cet article nécessite un abonnement.
Bienvenue sur EM-consulte, la référence des professionnels de santé.
L’achat d’article à l’unité est indisponible à l’heure actuelle.
Déjà abonné à cette revue ?