Bounds on an exponential sum arising in Boolean circuit complexity

Frederic Green; Amitabha Roy; Howard Straubing

doi:10.1016/j.crma.2005.07.011

Number Theory

Bounds on an exponential sum arising in Boolean circuit complexity

Presented by: Jean Bourgain

Frederic Green ¹; Amitabha Roy ²; Howard Straubing ²

¹ Department of Mathematics and Computer Science, Clark University, Worcester, MA 01610, USA
² Computer Science Department, Boston College, Chestnut Hill, MA 02467, USA

Comptes Rendus. Mathématique, Volume 341 (2005) no. 5, pp. 279-282

Abstract (Original language)
Résumé

We study exponential sums of the form $S = 2^{- n} \sum_{x \in {0, 1}^{n}} e_{m} (h (x)) e_{q} (p (x))$ , where $m, q \in Z^{+}$ are relatively prime, p is a polynomial with coefficients in $Z_{q}$ , and $h (x) = a (x_{1} + \dots + x_{n})$ 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} \sum_{x \in {0, 1}^{n}} e_{m} (h (x)) e_{q} (p (x))$ , où $m, q$ sont des entiers premiers entre eux, p est un polynôme à coefficients dans $Z_{q}$ et $h (x) = a (x_{1} + \dots + x_{n})$ , 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.

Received: 2005-06-02
Accepted: 2005-07-04
Published online: 2005-08-19

DOI: 10.1016/j.crma.2005.07.011

Author's affiliations:

Frederic Green ¹; Amitabha Roy ²; Howard Straubing ²

¹ Department of Mathematics and Computer Science, Clark University, Worcester, MA 01610, USA
² 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},
     year = {2005},
     publisher = {Elsevier},
     volume = {341},
     number = {5},
     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

References
Cited by

[1] N. Alon, R. Beigel, Lower bounds for approximation by low-degree polynomials over $Z_{n}$ , 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:

Comments - Policy