A note on the power of majority gates and modular gates

DOI10.1016/0020-0190(94)00221-JzbMath0875.68418OpenAlexW2011861941MaRDI QIDQ673905

Mikael Goldmann

Publication date: 28 February 1997

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0020-0190(94)00221-j

zbMATH Keywords

Computational complexityThreshold circuitsCircuit complexity

Mathematics Subject Classification ID

Mathematical problems of computer architecture (68M07) Computer system organization (68M99) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (4)

The correlation between parity and quadratic polynomials mod \(3\) ⋮ Upper and lower bounds for some depth-3 circuit classes ⋮ On the correlation between parity and modular polynomials ⋮ Depth Reduction for Circuits with a Single Layer of Modular Counting Gates

Cites Work

• Unnamed Item
• Unnamed Item
• On the power of small-depth threshold circuits
• \(\Sigma_ 1^ 1\)-formulae on finite structures
• Lower bounds on monotone complexity of the logical permanent
• The monotone circuit complexity of Boolean functions
• Lower bounds on the size of bounded depth circuits over a complete basis with logical addition
• Majority gates vs. general weighted threshold gates
• Depth reduction for circuits of unbounded fan-in
• The gap between monotone and non-monotone circuit complexity is exponential
• Parity, circuits, and the polynomial-time hierarchy
• Harmonic Analysis of Polynomial Threshold Functions

This page was built for publication: A note on the power of majority gates and modular gates