Computer Science
Bounds on an exponential sum arising in Boolean circuit complexity
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.
