Geodesic
Number Theory
Estimation of certain exponential sums arising in complexity theory
[Estimations de certaines sommes exponentielles en theorie de complexité]
Présenté par : Jean Bourgain
Bourgain, Jean 1
1 Institute for Advanced Study, Princeton, NJ 08540, USA
Comptes Rendus. Mathématique, Tome 340 (2005) no. 9, pp. 627-631 Cet article a éte moissonné depuis la source Numdam

Voir la notice de l'article

It is shown that the correlation on {0,1}n between parity and a polynomial p(x1,…,xn)∈Z[X1,…,Xn](modq), q a fixed odd number and p(X) of degree d arbitrary but fixed, is exponentially small in n as n→∞. An application to circuit complexity, from where the problem originates, is given.

On démontre que la corrélation sur {0,1}n de la fonction parité et un polynôme p(x1,…,xn)∈Z[X1,…,Xn](modq), q un entier impair donné et p(X) de degré d arbitraire mais fixé, est exponentiellement petite en n pour n→∞. On obient une application en théorie de complexité où la question trouve son origine.

Reçu le :
Accepté le :
Publié le :
DOI : 10.1016/j.crma.2005.03.008

Bourgain, Jean  1

1 Institute for Advanced Study, Princeton, NJ 08540, USA 
@article{CRMATH_2005__340_9_627_0,
     author = {Bourgain, Jean},
     title = {Estimation of certain exponential sums arising in complexity theory},
     journal = {Comptes Rendus. Math\'ematique},
     pages = {627--631},
     year = {2005},
     publisher = {Elsevier},
     volume = {340},
     number = {9},
     doi = {10.1016/j.crma.2005.03.008},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.1016/j.crma.2005.03.008/}
}
TY  - JOUR
AU  - Bourgain, Jean
TI  - Estimation of certain exponential sums arising in complexity theory
JO  - Comptes Rendus. Mathématique
PY  - 2005
SP  - 627
EP  - 631
VL  - 340
IS  - 9
PB  - Elsevier
UR  - http://geodesic.mathdoc.fr/articles/10.1016/j.crma.2005.03.008/
DO  - 10.1016/j.crma.2005.03.008
LA  - en
ID  - CRMATH_2005__340_9_627_0
ER  - 
%0 Journal Article
%A Bourgain, Jean
%T Estimation of certain exponential sums arising in complexity theory
%J Comptes Rendus. Mathématique
%D 2005
%P 627-631
%V 340
%N 9
%I Elsevier
%U http://geodesic.mathdoc.fr/articles/10.1016/j.crma.2005.03.008/
%R 10.1016/j.crma.2005.03.008
%G en
%F CRMATH_2005__340_9_627_0
Bourgain, Jean. Estimation of certain exponential sums arising in complexity theory. Comptes Rendus. Mathématique, Tome 340 (2005) no. 9, pp. 627-631. doi: 10.1016/j.crma.2005.03.008

Cité par Sources :