Paper Info
Title
Energy and fan-in of threshold circuits computing mod functions
Abstract
In this paper, we consider a threshold circuit C computing the modulus function MODm, and investigate a relationship between two complexity measures, fan-in l and energy e of C, where the fan-in l is defined to be the maximum number of inputs of every gate in C, and the energy e to be the maximum number of gates outputting "1" over all inputs to C. We first prove that MODm of n variables can be computed by a threshold circuit of fan-in l and energy e = O(n/l), and then provide an almost tight lower bound e = Ω((n - m)/l). Our results imply that there exists a tradeoff between the fan-in and energy of threshold circuits computing the modulus function.
Year
DOI
Venue
2011
10.1007/978-3-642-20877-5_16
TAMC
Keywords
Field
DocType
fan-in l,complexity measure,n variable,threshold circuit c,mod function,energy e,modulus function,maximum number,threshold circuit,boolean function,lower bound,fan in
Boolean function,Discrete mathematics,Mod,Combinatorics,Existential quantification,Upper and lower bounds,Fan-in,Electronic circuit,Modulo operation,Mathematics
Conference
Volume
ISSN
Citations 
6648
0302-9743
2
PageRank 
References 
Authors
0.38
10
3
Name
Order
Citations
PageRank
Akira Suzuki1518.44
Kei Uchizawa27412.89
Xiao Zhou332543.69