Bounds on an exponential sum arising in Boolean circuit complexity

DOI10.1016/J.CRMA.2005.07.011MaRDI QIDQ2565522zbMATH OpenOpenAlexFDO

Authors Frederic Green, Amitabha Roy, Howard Straubing

Publication date 27 September 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.07.011

Mathematics Subject Classification ID

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

Recommendations

• Estimation of certain exponential sums arising in complexity theory
• Exponential sums and circuits with a single threshold gate and mod-gates
• scientific article; zbMATH DE number 1559525
• Incomplete quadratic exponential sums in several variables
• On a small class of Boolean sums

Cites work

• Estimation of certain exponential sums arising in complexity theory
• Incomplete quadratic exponential sums in several variables
• The correlation between parity and quadratic polynomials mod \(3\)

Cited in

(10)

• Block-symmetric polynomials correlate with parity better than symmetric
• Correlation lower bounds from correlation upper bounds
• Upper Bounds on Boolean-Width with Applications to Exact Algorithms
• Depth reduction for composites
• Explicit lower bound of 4.5n - o(n) for boolena circuits
• Estimation of certain exponential sums arising in complexity theory
• Monomial Boolean functions with large high-order nonlinearities
• On the correlation between parity and modular polynomials
• Uniqueness of optimal mod 3 polynomials for parity
• An upper bound for the circuit complexity of existentially quantified Boolean formulas

This page was built for publication: Bounds on an exponential sum arising in Boolean circuit complexity

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