Estimation of certain exponential sums arising in complexity theory

DOI10.1016/J.CRMA.2005.03.008MaRDI QIDQ556911zbMATH OpenOpenAlexFDO

Authors 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)

Recommendations

• The correlation between parity and quadratic polynomials mod \(3\)
• Bounds on an exponential sum arising in Boolean circuit complexity
• On the Correlation Between Parity and Modular Polynomials
• On the correlation between parity and modular polynomials
• Exponential sums and circuits with a single threshold gate and mod-gates

Cites work

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

Cited in

(18)

• Uniqueness of optimal mod 3 polynomials for parity
• Block-symmetric polynomials correlate with parity better than symmetric
• Additive combinatorics: with a view towards computer science and cryptography -- an exposition
• On the correlation between parity and modular polynomials
• Correlation lower bounds from correlation upper bounds
• THE COMPLEXITY OF COMPUTING PARTIAL SUMS OFF-LINE
• scientific article; zbMATH DE number 7250146 (Why is no real title available?)
• Learning read-constant polynomials of constant degree modulo composites
• Circuit complexity of powering in fields of odd characteristic
• scientific article; zbMATH DE number 7528580 (Why is no real title available?)
• scientific article; zbMATH DE number 7650112 (Why is no real title available?)
• Learning Read-Constant Polynomials of Constant Degree Modulo Composites
• Monomial Boolean functions with large high-order nonlinearities
• Bounds on an exponential sum arising in Boolean circuit complexity
• Depth reduction for composites
• Exponential bounds for normal approximation of the number of descents and inversions
• Correlation bounds for poly-size \(\mathrm{AC}^0\) circuits with \(n^{1 - o(1)}\) symmetric gates
• Incomplete quadratic exponential sums in several variables

This page was built for publication: Estimation of certain exponential sums arising in complexity theory

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q556911)