A weight-size trade-off for circuits with MOD m gates

DOI10.1145/195058.195108zbMath1345.68159OpenAlexW2078561064MaRDI QIDQ2817598

Vince Grolmusz

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.195108

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (7)

The correlation between parity and quadratic polynomials mod \(3\) ⋮ Upper and lower bounds for some depth-3 circuit classes ⋮ On the power of circuits with gates of low \(L_{1}\) norms. ⋮ Harmonic analysis, real approximation, and the communication complexity of Boolean functions ⋮ On the correlation between parity and modular polynomials ⋮ On the computational power of depth-2 circuits with threshold and modulo gates ⋮ Depth Reduction for Circuits with a Single Layer of Modular Counting Gates

This page was built for publication: A weight-size trade-off for circuits with MOD m gates