no. 5
Number Theory
Bounds on an exponential sum arising in Boolean circuit complexity
[Bornes sur une somme exponentielle liée à la complexité des circuits booléens]
Présenté par : Jean Bourgain
Green, Frederic1 ; Roy, Amitabha2 ; Straubing, Howard2
1 Department of Mathematics and Computer Science, Clark University, Worcester, MA 01610, USA
2 Computer Science Department, Boston College, Chestnut Hill, MA 02467, USA
Comptes Rendus. Mathématique, Tome 341 (2005) no. 5, pp. 279-282

We study exponential sums of the form S=2−n∑x∈{0,1}nem(h(x))eq(p(x)), where m,q∈Z+ are relatively prime, p is a polynomial with coefficients in Zq, and h(x)=a(x1+⋯+xn) for some 1⩽a<m. We prove an upper bound of the form 2−Ω(n) on |S|. 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.

On étudie les sommes exponentielles de la forme S=2−n∑x∈{0,1}nem(h(x))eq(p(x)), où m,q sont des entiers premiers entre eux, p est un polynôme à coefficients dans Zq et h(x)=a(x1+⋯+xn), avec 1⩽a<m. On démontre que |S|<2−Ω(n). 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.

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

Green, Frederic 1 ; Roy, Amitabha 2 ; Straubing, Howard 2

1 Department of Mathematics and Computer Science, Clark University, Worcester, MA 01610, USA
2 Computer Science Department, Boston College, Chestnut Hill, MA 02467, USA 
@article{CRMATH_2005__341_5_279_0,
     author = {Green, Frederic and Roy, Amitabha and Straubing, Howard},
     title = {Bounds on an exponential sum arising in {Boolean} circuit complexity},
     journal = {Comptes Rendus. Math\'ematique},
     pages = {279--282},
     year = {2005},
     publisher = {Elsevier},
     volume = {341},
     number = {5},
     doi = {10.1016/j.crma.2005.07.011},
     language = {en},
     url = {https://www.numdam.org/articles/10.1016/j.crma.2005.07.011/}
}
TY  - JOUR
AU  - Green, Frederic
AU  - Roy, Amitabha
AU  - Straubing, Howard
TI  - Bounds on an exponential sum arising in Boolean circuit complexity
JO  - Comptes Rendus. Mathématique
PY  - 2005
SP  - 279
EP  - 282
VL  - 341
IS  - 5
PB  - Elsevier
UR  - https://www.numdam.org/articles/10.1016/j.crma.2005.07.011/
DO  - 10.1016/j.crma.2005.07.011
LA  - en
ID  - CRMATH_2005__341_5_279_0
ER  - 
%0 Journal Article
%A Green, Frederic
%A Roy, Amitabha
%A Straubing, Howard
%T Bounds on an exponential sum arising in Boolean circuit complexity
%J Comptes Rendus. Mathématique
%D 2005
%P 279-282
%V 341
%N 5
%I Elsevier
%U https://www.numdam.org/articles/10.1016/j.crma.2005.07.011/
%R 10.1016/j.crma.2005.07.011
%G en
%F CRMATH_2005__341_5_279_0
Green, Frederic; Roy, Amitabha; Straubing, Howard. Bounds on an exponential sum arising in Boolean circuit complexity. Comptes Rendus. Mathématique, Tome 341 (2005) no. 5, pp. 279-282. doi: 10.1016/j.crma.2005.07.011

[1] N. Alon, R. Beigel, Lower bounds for approximation by low-degree polynomials over Zn, in: Annual IEEE Conference on Computational Complexity, vol. 16, 2001

[2] Bourgain, J. Estimation of certain exponential sums arising in complexity theory, C. R. Acad. Sci. Paris, Ser. I, Volume 340 (2005), pp. 627-631

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

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

Cité par Sources :