Exponential sums and circuits with a single threshold gate and mod-gates

DOI10.1007/S002240000126MaRDI QIDQ1293551zbMATH OpenOpenAlexFDO

Authors K. Appert

Publication date 13 June 2000

Published in Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s002240000126

zbMATH Keywords

complexity theorybounded-depth circuits

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Recommendations

• On the computational power of depth-2 circuits with threshold and modulo gates
• Exponential lower bound for bounded depth circuits with few threshold gates
• Lower bounds for modular counting by circuits with modular gates
• Lower bounds for modular counting by circuits with modular gates

Cited in

(9)

• Block-symmetric polynomials correlate with parity better than symmetric
• On the correlation between parity and modular polynomials
• Exponential lower bound for bounded depth circuits with few threshold gates
• Correlation lower bounds from correlation upper bounds
• Estimation of certain exponential sums arising in complexity theory
• Lower bounds for modular counting by circuits with modular gates
• The correlation between parity and quadratic polynomials mod \(3\)
• Bounds on an exponential sum arising in Boolean circuit complexity
• Incomplete quadratic exponential sums in several variables

This page was built for publication: Exponential sums and circuits with a single threshold gate and mod-gates

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