Blog Archives

Lower Bounds Against Circuits with Modular Gates

The modular gate MODm, for any integer \(m\), outputs 0 if the sum of its inputs is 0 modulo \(m\), and outputs 1 otherwise. An ACC[m] circuit is a circuit with NOT gates and unbounded fan-in AND, OR, and MODm

Tagged with: ,
Posted in Theory