2026-07-22T12:28:38Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:13398 2024-03-06T10:51:53Z ddc:004 open_access

Size, Depth and Energy of Threshold Circuits Computing Parity Function Uchizawa, Kei Circuit complexity neural networks threshold circuits sprase activity tradeoffs We investigate relations among the size, depth and energy of threshold circuits computing the n-variable 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 depth-2 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 depth-2 threshold circuit of size O(2^{n-2e}) and energy e; - PAR_n is computable by a depth-3 threshold circuit of size O(2^{n/(e-1)} + 2^{e-2}) and energy e; and - PAR_n is computable by a threshold circuit of size O((e+d)2^{n-m}), depth d + O(1) and energy e + O(1), where m = max (((e-1)/(d-1))^{d-1}, ((d-1)/(e-1))^{e-1}). 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Kei Uchizawa 2020 Is Part Of LIPIcs, Volume 181, 31st International Symposium on Algorithms and Computation (ISAAC 2020) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ISAAC.2020.54 urn:nbn:de:0030-drops-133988 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2020.54 eng https://creativecommons.org/licenses/by/3.0/legalcode