On the computational power of depth 2 circuits with threshold and modulo gates
From MaRDI portal
Publication:2817596
DOI10.1145/195058.195103zbMath1345.68130OpenAlexW2097957732MaRDI QIDQ2817596
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
Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Related Items
The correlation between parity and quadratic polynomials mod \(3\), On the power of a threshold gate at the top, MODp-tests, almost independence and small probability spaces, An efficient membership-query algorithm for learning DNF with respect to the uniform distribution, Unnamed Item, On the correlation between parity and modular polynomials, On the computational power of depth-2 circuits with threshold and modulo gates, Lower bounds for modular counting by circuits with modular gates, Learning DNF from random walks, Languages defined with modular counting quantifiers