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

DOI10.1007/S002240000126zbMATH Open0937.68051OpenAlexW1969981165MaRDI QIDQ1293551FDOQ1293551

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

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

zbMATH Keywords

complexity theorybounded-depth circuits

Mathematics Subject Classification ID

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

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)