Number Theory
Bounds on an exponential sum arising in Boolean circuit complexity
Comptes Rendus. Mathématique, Volume 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. 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. 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.

Accepted:
Published online:
DOI: 10.1016/j.crma.2005.07.011

Frederic Green 1; Amitabha Roy 2; Howard Straubing 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 = {Frederic Green and Amitabha Roy and Howard Straubing},
title = {Bounds on an exponential sum arising in {Boolean} circuit complexity},
journal = {Comptes Rendus. Math\'ematique},
pages = {279--282},
publisher = {Elsevier},
volume = {341},
number = {5},
year = {2005},
doi = {10.1016/j.crma.2005.07.011},
language = {en},
}
TY  - JOUR
AU  - Frederic Green
AU  - Amitabha Roy
AU  - Howard Straubing
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
DO  - 10.1016/j.crma.2005.07.011
LA  - en
ID  - CRMATH_2005__341_5_279_0
ER  - 
%0 Journal Article
%A Frederic Green
%A Amitabha Roy
%A Howard Straubing
%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
%R 10.1016/j.crma.2005.07.011
%G en
%F CRMATH_2005__341_5_279_0
Frederic Green; Amitabha Roy; Howard Straubing. Bounds on an exponential sum arising in Boolean circuit complexity. Comptes Rendus. Mathématique, Volume 341 (2005) no. 5, pp. 279-282. doi : 10.1016/j.crma.2005.07.011. https://comptes-rendus.academie-sciences.fr/mathematique/articles/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] J. Bourgain 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] F. Green The correlation between parity and quadratic polynomials mod 3, J. Comput. System Sci., Volume 69 (2004) no. 1, pp. 28-44

Cited by Sources: