{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,7,19]],"date-time":"2024-07-19T19:54:07Z","timestamp":1721418847790},"reference-count":11,"publisher":"World Scientific Pub Co Pte Lt","issue":"01","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Found. Comput. Sci."],"published-print":{"date-parts":[[2013,1]]},"abstract":"<jats:p> We prove that the modulus function MOD<jats:sub>m<\/jats:sub> of n variables can be computed by a threshold circuit C of energy e and size s = O(e(n\/m)<jats:sup>1\/(e \u2212 1)<\/jats:sup>) for any integer e \u2265 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 = \u03a9(e(n\/m)<jats:sup>1\/e<\/jats:sup>). We also consider an extreme case where threshold circuits have energy 1, and prove that such circuits need at least 2<jats:sup>(n \u2212 m)\/2<\/jats:sup> gates to compute MOD<jats:sub>m<\/jats:sub> of n variables. <\/jats:p>","DOI":"10.1142\/s0129054113400029","type":"journal-article","created":{"date-parts":[[2013,5,14]],"date-time":"2013-05-14T02:54:44Z","timestamp":1368500084000},"page":"15-29","source":"Crossref","is-referenced-by-count":4,"title":["ENERGY-EFFICIENT THRESHOLD CIRCUITS COMPUTING MOD FUNCTIONS"],"prefix":"10.1142","volume":"24","author":[{"given":"AKIRA","family":"SUZUKI","sequence":"first","affiliation":[{"name":"Graduate School of Information Sciences, Tohoku University, Aramaki-aza Aoba 6-6-05, Aoba-ku, Sendai, 980-8579, Japan"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"KEI","family":"UCHIZAWA","sequence":"additional","affiliation":[{"name":"Graduate School of Information Sciences, Tohoku University, Aramaki-aza Aoba 6-6-05, Aoba-ku, Sendai, 980-8579, Japan"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"XIAO","family":"ZHOU","sequence":"additional","affiliation":[{"name":"Graduate School of Information Sciences, Tohoku University, Aramaki-aza Aoba 6-6-05, Aoba-ku, Sendai, 980-8579, Japan"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"219","published-online":{"date-parts":[[2013,5,13]]},"reference":[{"key":"p_1","doi-asserted-by":"publisher","DOI":"10.1097\/00004647-200110000-00001"},{"key":"p_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0960-9822(03)00135-0"},{"key":"p_3","first-page":"1064","volume":"1","author":"F\u00f6ldiak P.","year":"2003","journal-title":"The Handbook of Brain Theory and Neural Networks"},{"key":"p_4","doi-asserted-by":"publisher","DOI":"10.1126\/science.1089662"},{"key":"p_5","doi-asserted-by":"publisher","DOI":"10.1016\/j.conb.2004.07.007"},{"key":"p_6","doi-asserted-by":"publisher","DOI":"10.1126\/science.287.5456.1273"},{"key":"p_7","doi-asserted-by":"publisher","DOI":"10.1162\/neco.2006.18.12.2994"},{"key":"p_10","doi-asserted-by":"publisher","DOI":"10.1162\/089976603322518731"},{"key":"p_12","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2010.08.006"},{"key":"p_13","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2008.07.028"},{"key":"p_14","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2010.11.022"}],"container-title":["International Journal of Foundations of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0129054113400029","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,7]],"date-time":"2019-08-07T10:45:20Z","timestamp":1565174720000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0129054113400029"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,1]]},"references-count":11,"journal-issue":{"issue":"01","published-online":{"date-parts":[[2013,5,13]]},"published-print":{"date-parts":[[2013,1]]}},"alternative-id":["10.1142\/S0129054113400029"],"URL":"https:\/\/doi.org\/10.1142\/s0129054113400029","relation":{},"ISSN":["0129-0541","1793-6373"],"issn-type":[{"value":"0129-0541","type":"print"},{"value":"1793-6373","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013,1]]}}}