IEICE TRANSACTIONS on Fundamentals
Computational Power of Threshold Circuits of Energy at most Two
Summary :
The energy of a threshold circuit C is defined to be the maximum number of gates outputting ones for an input assignment, where the maximum is taken over all the input assignments. In this paper, we study computational power of threshold circuits of energy at most two. We present several results showing that the computational power of threshold circuits of energy one and the counterpart of energy two are remarkably different. In particular, we give an explicit function which requires an exponential size for threshold circuits of energy one, but is computable by a threshold circuit of size just two and energy two. We also consider MOD functions and Generalized Inner Product functions, and show that these functions also require exponential size for threshold circuits of energy one, but are computable by threshold circuits of substantially less size and energy two.
- Publication
- IEICE TRANSACTIONS on Fundamentals Vol.E101-A No.9 pp.1431-1439
- Publication Date
- 2018/09/01
- Publicized
- Online ISSN
- 1745-1337
- DOI
- 10.1587/transfun.E101.A.1431
- Type of Manuscript
- Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
- Category
Authors
Hiroki MANIWA
Tohoku University
Takayuki OKI
Yamagata University
Akira SUZUKI
Tohoku University
Kei UCHIZAWA
Yamagata University
Xiao ZHOU
Tohoku University
Keyword
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Cite this
Copy
Hiroki MANIWA, Takayuki OKI, Akira SUZUKI, Kei UCHIZAWA, Xiao ZHOU, "Computational Power of Threshold Circuits of Energy at most Two" in IEICE TRANSACTIONS on Fundamentals,
vol. E101-A, no. 9, pp. 1431-1439, September 2018, doi: 10.1587/transfun.E101.A.1431.
Abstract: The energy of a threshold circuit C is defined to be the maximum number of gates outputting ones for an input assignment, where the maximum is taken over all the input assignments. In this paper, we study computational power of threshold circuits of energy at most two. We present several results showing that the computational power of threshold circuits of energy one and the counterpart of energy two are remarkably different. In particular, we give an explicit function which requires an exponential size for threshold circuits of energy one, but is computable by a threshold circuit of size just two and energy two. We also consider MOD functions and Generalized Inner Product functions, and show that these functions also require exponential size for threshold circuits of energy one, but are computable by threshold circuits of substantially less size and energy two.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/transfun.E101.A.1431/_p
Copy
@ARTICLE{e101-a_9_1431,
author={Hiroki MANIWA, Takayuki OKI, Akira SUZUKI, Kei UCHIZAWA, Xiao ZHOU, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={Computational Power of Threshold Circuits of Energy at most Two},
year={2018},
volume={E101-A},
number={9},
pages={1431-1439},
abstract={The energy of a threshold circuit C is defined to be the maximum number of gates outputting ones for an input assignment, where the maximum is taken over all the input assignments. In this paper, we study computational power of threshold circuits of energy at most two. We present several results showing that the computational power of threshold circuits of energy one and the counterpart of energy two are remarkably different. In particular, we give an explicit function which requires an exponential size for threshold circuits of energy one, but is computable by a threshold circuit of size just two and energy two. We also consider MOD functions and Generalized Inner Product functions, and show that these functions also require exponential size for threshold circuits of energy one, but are computable by threshold circuits of substantially less size and energy two.},
keywords={},
doi={10.1587/transfun.E101.A.1431},
ISSN={1745-1337},
month={September},}
Copy
TY - JOUR
TI - Computational Power of Threshold Circuits of Energy at most Two
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 1431
EP - 1439
AU - Hiroki MANIWA
AU - Takayuki OKI
AU - Akira SUZUKI
AU - Kei UCHIZAWA
AU - Xiao ZHOU
PY - 2018
DO - 10.1587/transfun.E101.A.1431
JO - IEICE TRANSACTIONS on Fundamentals
SN - 1745-1337
VL - E101-A
IS - 9
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - September 2018
AB - The energy of a threshold circuit C is defined to be the maximum number of gates outputting ones for an input assignment, where the maximum is taken over all the input assignments. In this paper, we study computational power of threshold circuits of energy at most two. We present several results showing that the computational power of threshold circuits of energy one and the counterpart of energy two are remarkably different. In particular, we give an explicit function which requires an exponential size for threshold circuits of energy one, but is computable by a threshold circuit of size just two and energy two. We also consider MOD functions and Generalized Inner Product functions, and show that these functions also require exponential size for threshold circuits of energy one, but are computable by threshold circuits of substantially less size and energy two.
ER -
English
