Energy-Efficient Threshold Circuits Computing Mod Functions

Suzuki, A., Uchizawa, K. and Zhou, X.

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

Cite as: Suzuki, A., Uchizawa, K. and Zhou, X. (2011). Energy-Efficient Threshold Circuits Computing Mod Functions. In Proc. Computing: The Australasian Theory Symposium (CATS 2011) Perth, Australia. CRPIT, 119. Alex Potanin and Taso Viglas Eds., ACS. 105-110

(from crpit.com) (local if available)