Bounds on an exponential sum arising in Boolean circuit complexity

Authors

Frederic Green, Clark UniversityFollow
Amitabha Roy, Boston College
Howard Straubing, Boston College

Document Type

Article

Abstract

We study exponential sums of the form S = 2-n ∑x∈{0,1}n em (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. © Académie des sciences. Published by Elsevier SAS. All rights reserved.

Publication Title

Comptes Rendus Mathematique

Publication Date

2005

Volume

341

Issue

5

First Page

279

Last Page

282

ISSN

1631-073X

DOI

10.1016/j.crma.2005.07.011

Repository Citation

Green, Frederic; Roy, Amitabha; and Straubing, Howard, "Bounds on an exponential sum arising in Boolean circuit complexity" (2005). Computer Science. 58.
https://commons.clarku.edu/faculty_computer_sciences/58

APA Citation

Green, F., Roy, A., & Straubing, H. (2005). Bounds on an exponential sum arising in Boolean circuit complexity. Comptes Rendus Mathematique, 341(5), 279-282.