Estimation of certain exponential sums arising in complexity theory

DOI10.1016/J.CRMA.2005.03.008zbMATH Open1112.11038OpenAlexW2059892717MaRDI QIDQ556911FDOQ556911

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

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

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (18)

• Block-symmetric polynomials correlate with parity better than symmetric
• Uniqueness of optimal mod 3 polynomials for parity
• Additive combinatorics: with a view towards computer science and cryptography -- an exposition
• On the correlation between parity and modular polynomials
• THE COMPLEXITY OF COMPUTING PARTIAL SUMS OFF-LINE
• Correlation lower bounds from correlation upper bounds
• Title not available (Why is that?)
• Learning read-constant polynomials of constant degree modulo composites
• Circuit complexity of powering in fields of odd characteristic
• Title not available (Why is that?)
• Title not available (Why is that?)
• 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)