Estimation of certain exponential sums arising in complexity theory

Bourgain, Jean

doi:10.1016/j.crma.2005.03.008

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 ¹

¹ Institute for Advanced Study, Princeton, NJ 08540, USA

Comptes Rendus. Mathématique, Tome 340 (2005) no. 9, pp. 627-631.

Résumé
Abstract

On démontre que la corrélation sur ${0, 1}^{n}$ de la fonction parité et un polynôme $p (x_{1}, \dots, x_{n}) \in Z [X_{1}, \dots, X_{n}] (\mod q)$ , q un entier impair donné et $p (X)$ de degré d arbitraire mais fixé, est exponentiellement petite en n pour $n \to \infty$ . On obient une application en théorie de complexité où la question trouve son origine.

It is shown that the correlation on ${0, 1}^{n}$ between parity and a polynomial $p (x_{1}, \dots, x_{n}) \in Z [X_{1}, \dots, X_{n}] (\mod q)$ , q a fixed odd number and $p (X)$ of degree d arbitrary but fixed, is exponentially small in n as $n \to \infty$ . An application to circuit complexity, from where the problem originates, is given.

Reçu le : 2005-02-03
Accepté le : 2005-03-01
Publié le : 2005-04-27

DOI : 10.1016/j.crma.2005.03.008

Affiliations des auteurs :

Bourgain, Jean ¹

¹ 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},
     publisher = {Elsevier},
     volume = {340},
     number = {9},
     year = {2005},
     doi = {10.1016/j.crma.2005.03.008},
     language = {en},
     url = {http://archive.numdam.org/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://archive.numdam.org/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://archive.numdam.org/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. http://archive.numdam.org/articles/10.1016/j.crma.2005.03.008/

Bibliographie
Cité par

[1] Alon, N.; Beigel, R. Lower bounds for approximation by low degree polynomials over $Z_{m}$ , Annual IEEE Conference on Computational Complexity (formerly Annual Conference on Structure in Complexity Theory), vol. 16, 2001

[2] Cai, J.-Y.; Green, F.; Thierauf, T. On the correlation of symmetric functions, Math. Systems Theory, Volume 29 (1996) no. 3, pp. 245-258

[3] E. Dueñez, S. Miller, A. Roy, H. Straubing Incomplete quadratic exponential sums in several variables, preprint

[4] Green, F. The correlation between parity and quadratic polynomials mod3, J. Comput. System Sci., Volume 69 (2004) no. 1, pp. 28-44

[5] Hajnal, A.; Maass, W.; Pudlák, P.; Szegedy, M.; Turán, G. Threshold circuits of bounded depth, J. Comput. System Sci., Volume 46 (1993) no. 2, pp. 129-154

Cité par Sources :