On the computational power of depth 2 circuits with threshold and modulo gates

DOI10.1145/195058.195103MaRDI QIDQ2817596zbMATHOpenAlexFDO

Authors Matthias Krause, Pavel Pudlák

Publication date 1 September 2016

Published in Proceedings of the twenty-sixth annual ACM symposium on Theory of computing - STOC '94 (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/195058.195103

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Recommendations

• On the computational power of depth-2 circuits with threshold and modulo gates
• A note on the power of majority gates and modular gates
• scientific article; zbMATH DE number 2011859
• Lower bounds for modular counting by circuits with modular gates
• Lower bounds for modular counting by circuits with modular gates

Cited in

(19)

• On the power of small-depth threshold circuits
• Lower bounds for modular counting by circuits with modular gates
• On the power of a threshold gate at the top
• An efficient membership-query algorithm for learning DNF with respect to the uniform distribution
• Learning DNF from random walks
• Languages defined with modular counting quantifiers
• Computing threshold functions by depth-3 threshold circuits with smaller thresholds of their gates
• Depth Reduction for Circuits with a Single Layer of Modular Counting Gates
• On the computational power of depth-2 circuits with threshold and modulo gates
• Lower bounds for depth-three circuits with equals and Mod-gates
• Powering requires threshold depth 3
• On the correlation between parity and modular polynomials
• A note on a theorem of Barrington, Straubing and Thérien
• On realizing iterated multiplication by small depth threshold circuits
• Circuit complexity before the dawn of the new millennium
• \(\mathrm{MOD}_p\)-tests, almost independence and small probability spaces (extended abstract)
• The correlation between parity and quadratic polynomials mod \(3\)
• Mathematical Foundations of Computer Science 2005
• scientific article; zbMATH DE number 1496576 (Why is no real title available?)

This page was built for publication: On the computational power of depth 2 circuits with threshold and modulo gates

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