We prove that the modulus function MODm of n variables can be computed by a threshold circuit C of energy e and size s = O(e(n/m) 1/(e - 1)) for any integer e ≥ 2, where the energy e is defined to be the maximum number of gates outputting "1" over all inputs to C, and the size s to be the number of gates in C. Our upper bound on the size s almost matches the known lower bound s = Ω(e(n/m)1/e). We also consider an extreme case where threshold circuits have energy 1, and prove that such circuits need at least 2(n - m)/2 gates to compute MOD m of n variables.
|Number of pages||15|
|Journal||International Journal of Foundations of Computer Science|
|Publication status||Published - 2013 Jan|
- Circuit complexity
- Energy complexity
- Neural networks
- Threshold circuits