TY - GEN
T1 - Energy-efficient threshold circuits computing MOD functions
AU - Suzuki, Akira
AU - Uchizawa, Kei
AU - Zhou, Xiao
PY - 2011/12/1
Y1 - 2011/12/1
N2 - We prove that the modulus function MOD m 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).
AB - We prove that the modulus function MOD m 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).
UR - http://www.scopus.com/inward/record.url?scp=84864628714&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84864628714&partnerID=8YFLogxK
M3 - Conference contribution
AN - SCOPUS:84864628714
SN - 9781920682989
T3 - Conferences in Research and Practice in Information Technology Series
SP - 105
EP - 110
BT - Theory of Computing 2011 - Proceedings of the 17th Computing
T2 - Theory of Computing 2011 - 17th Computing: The Australasian Theory Symposium, CATS 2011
Y2 - 17 January 2011 through 20 January 2011
ER -