Abstract
We investigate relations among the size, depth and energy of threshold circuits computing the nvariable parity function PAR_n, where the energy is a complexity measure for sparsity on computation of threshold circuits, and is defined to be the maximum number of gates outputting "1" over all the input assignments. We show that PAR_n is hard for threshold circuits of small size, depth and energy:
 If a depth2 threshold circuit C of size s and energy e computes PAR_n, it holds that 2^{n/(elog ^e n)} ≤ s; and
 if a threshold circuit C of size s, depth d and energy e computes PAR_n, it holds that 2^{n/(e2^{e+d}log ^e n)} ≤ s. We then provide several upper bounds:
 PAR_n is computable by a depth2 threshold circuit of size O(2^{n2e}) and energy e;
 PAR_n is computable by a depth3 threshold circuit of size O(2^{n/(e1)} + 2^{e2}) and energy e; and
 PAR_n is computable by a threshold circuit of size O((e+d)2^{nm}), depth d + O(1) and energy e + O(1), where m = max (((e1)/(d1))^{d1}, ((d1)/(e1))^{e1}). Our lower and upper bounds imply that threshold circuits need exponential size if both depth and energy are constant, which contrasts with the fact that PAR_n is computable by a threshold circuit of size O(n) and depth 2 if there is no restriction on the energy. Our results also suggest that any threshold circuit computing the parity function needs depth to be sparse if its size is bounded.
BibTeX  Entry
@InProceedings{uchizawa:LIPIcs:2020:13398,
author = {Kei Uchizawa},
title = {{Size, Depth and Energy of Threshold Circuits Computing Parity Function}},
booktitle = {31st International Symposium on Algorithms and Computation (ISAAC 2020)},
pages = {54:154:13},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771733},
ISSN = {18688969},
year = {2020},
volume = {181},
editor = {Yixin Cao and SiuWing Cheng and Minming Li},
publisher = {Schloss DagstuhlLeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/13398},
URN = {urn:nbn:de:0030drops133988},
doi = {10.4230/LIPIcs.ISAAC.2020.54},
annote = {Keywords: Circuit complexity, neural networks, threshold circuits, sprase activity, tradeoffs}
}
Keywords: 

Circuit complexity, neural networks, threshold circuits, sprase activity, tradeoffs 
Collection: 

31st International Symposium on Algorithms and Computation (ISAAC 2020) 
Issue Date: 

2020 
Date of publication: 

04.12.2020 