TY - JOUR

T1 - Energy and fan-in of logic circuits computing symmetric Boolean functions

AU - Suzuki, Akira

AU - Uchizawa, Kei

AU - Zhou, Xiao

N1 - Funding Information:
We would like to thank the referees for their helpful suggestions and comments. The first author was supported by JSPS Grant-in-Aid for JSPS Fellows No. 24.3660. The second author was supported by JSPS Grant-in-Aid for Young Scientists (B) No. 23700003.

PY - 2013

Y1 - 2013

N2 - In this paper, we consider a logic circuit (i.e., a combinatorial circuit consisting of gates, each of which computes a Boolean function) C computing a symmetric Boolean function f, and investigate a relationship between two complexity measures, energy e and fan-in l of C, where the energy e is the maximum number of gates outputting "1" over all inputs to C, and the fan-in l is the maximum number of inputs of every gate in C. We first prove that any symmetric Boolean function f of n variables can be computed by a logic circuit of energy e=O(n/l) and fan-in l, and then provide an almost tight lower bound e≥âŒ̂(n-mf)/lâŒ‰ where mf is the maximum numbers of consecutive "0"s or "1"s in the value vector of f. Our results imply that there exists a tradeoff between the energy and fan-in of logic circuits computing a symmetric Boolean function.

AB - In this paper, we consider a logic circuit (i.e., a combinatorial circuit consisting of gates, each of which computes a Boolean function) C computing a symmetric Boolean function f, and investigate a relationship between two complexity measures, energy e and fan-in l of C, where the energy e is the maximum number of gates outputting "1" over all inputs to C, and the fan-in l is the maximum number of inputs of every gate in C. We first prove that any symmetric Boolean function f of n variables can be computed by a logic circuit of energy e=O(n/l) and fan-in l, and then provide an almost tight lower bound e≥âŒ̂(n-mf)/lâŒ‰ where mf is the maximum numbers of consecutive "0"s or "1"s in the value vector of f. Our results imply that there exists a tradeoff between the energy and fan-in of logic circuits computing a symmetric Boolean function.

KW - Boolean functions

KW - Energy complexity

KW - Fan-in

KW - MOD functions

KW - Parity function

KW - Symmetric functions

KW - Threshold circuits

UR - http://www.scopus.com/inward/record.url?scp=84885018458&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84885018458&partnerID=8YFLogxK

U2 - 10.1016/j.tcs.2012.11.039

DO - 10.1016/j.tcs.2012.11.039

M3 - Article

AN - SCOPUS:84885018458

SN - 0304-3975

VL - 505

SP - 74

EP - 80

JO - Theoretical Computer Science

JF - Theoretical Computer Science

ER -