Estimation of certain exponential sums arising in complexity theory

DOI10.1016/j.crma.2005.03.008zbMath1112.11038OpenAlexW2059892717MaRDI QIDQ556911

Jean Bourgain

Publication date: 23 June 2005

Published in: Comptes Rendus. Mathématique. Académie des Sciences, Paris (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.crma.2005.03.008

Mathematics Subject Classification ID

Estimates on exponential sums (11L07) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items

Correlation lower bounds from correlation upper bounds, Block-symmetric polynomials correlate with parity better than symmetric, Unnamed Item, Monomial Boolean functions with large high-order nonlinearities, Depth Reduction for Composites, Learning Read-Constant Polynomials of Constant Degree Modulo Composites, Uniqueness of optimal mod 3 polynomials for parity, On the correlation between parity and modular polynomials, Learning read-constant polynomials of constant degree modulo composites, Unnamed Item, Correlation Bounds for Poly-size $\mbox{\rm AC}^0$ Circuits with n 1 − o(1) Symmetric Gates, Unnamed Item, Additive Combinatorics: With a View Towards Computer Science and Cryptography—An Exposition, Bounds on an exponential sum arising in Boolean circuit complexity, Incomplete quadratic exponential sums in several variables

Cites Work

• The correlation between parity and quadratic polynomials mod \(3\)
• Threshold circuits of bounded depth
• On the correlation of symmetric functions