Search Results

Documents authored by Uchizawa, Kei

Document
DOI: 10.4230/LIPIcs.MFCS.2023.85
Exponential Lower Bounds for Threshold Circuits of Sub-Linear Depth and Energy

Authors: Kei Uchizawa and Haruki Abe

Published in: LIPIcs, Volume 272, 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)

Abstract
In this paper, we investigate computational power of threshold circuits and other theoretical models of neural networks in terms of the following four complexity measures: size (the number of gates), depth, weight and energy. Here, the energy of a circuit measures sparsity of their computation, and is defined as the maximum number of gates outputting non-zero values taken over all the input assignments. As our main result, we prove that any threshold circuit C of size s, depth d, energy e and weight w satisfies log(rk(M_C)) ≤ ed (log s + log w + log n), where rk(M_C) is the rank of the communication matrix M_C of a 2n-variable Boolean function that C computes. Thus, such a threshold circuit C is able to compute only a Boolean function of which communication matrix has rank bounded by a product of logarithmic factors of s, w and linear factors of d, e. This implies an exponential lower bound on the size of even sublinear-depth and sublinear-energy threshold circuit. For example, we can obtain an exponential lower bound s = 2^Ω(n^{1/3}) for threshold circuits of depth n^{1/3}, energy n^{1/3} and weight 2^o(n^{1/3}). We also show that the inequality is tight up to a constant factor when the depth d and energy e satisfies ed = o(n/log n). For other models of neural networks such as a discretized ReLU circuits and descretized sigmoid circuits, we define energy as the maximum number of gates outputting non-zero values. We then prove that a similar inequality also holds for a discretized circuit C: rk(M_C) = O(ed(log s + log w + log n)³). Thus, if we consider the number gates outputting non-zero values as a measure for sparse activity of a neural network, our results suggest that larger depth linearly helps neural networks to acquire sparse activity.
Cite as

Kei Uchizawa and Haruki Abe. Exponential Lower Bounds for Threshold Circuits of Sub-Linear Depth and Energy. In 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 272, pp. 85:1-85:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{uchizawa_et_al:LIPIcs.MFCS.2023.85,
  author =	{Uchizawa, Kei and Abe, Haruki},
  title =	{{Exponential Lower Bounds for Threshold Circuits of Sub-Linear Depth and Energy}},
  booktitle =	{48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)},
  pages =	{85:1--85:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-292-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{272},
  editor =	{Leroux, J\'{e}r\^{o}me and Lombardy, Sylvain and Peleg, David},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2023.85},
  URN =		{urn:nbn:de:0030-drops-186192},
  doi =		{10.4230/LIPIcs.MFCS.2023.85},
  annote =	{Keywords: Circuit complexity, disjointness function, equality function, neural networks, threshold circuits, ReLU cicuits, sigmoid circuits, sparse activity}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2020.54
Size, Depth and Energy of Threshold Circuits Computing Parity Function

Authors: Kei Uchizawa

Published in: LIPIcs, Volume 181, 31st International Symposium on Algorithms and Computation (ISAAC 2020)

Abstract
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.
Cite as

Kei Uchizawa. Size, Depth and Energy of Threshold Circuits Computing Parity Function. In 31st International Symposium on Algorithms and Computation (ISAAC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 181, pp. 54:1-54:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{uchizawa:LIPIcs.ISAAC.2020.54,
  author =	{Uchizawa, Kei},
  title =	{{Size, Depth and Energy of Threshold Circuits Computing Parity Function}},
  booktitle =	{31st International Symposium on Algorithms and Computation (ISAAC 2020)},
  pages =	{54:1--54:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-173-3},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{181},
  editor =	{Cao, Yixin and Cheng, Siu-Wing and Li, Minming},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2020.54},
  URN =		{urn:nbn:de:0030-drops-133988},
  doi =		{10.4230/LIPIcs.ISAAC.2020.54},
  annote =	{Keywords: Circuit complexity, neural networks, threshold circuits, sprase activity, tradeoffs}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2020.76
Synchronous Boolean Finite Dynamical Systems on Directed Graphs over XOR Functions

Authors: Mitsunori Ogihara and Kei Uchizawa

Published in: LIPIcs, Volume 170, 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)

Abstract
In this paper, we investigate the complexity of a number of computational problems defined on a synchronous boolean finite dynamical system, where update functions are chosen from a template set of exclusive-or and its negation. We first show that the reachability and path-intersection problems are solvable in logarithmic space-uniform AC¹ if the objects execute permutations, while the reachability problem is known to be in P and the path-intersection problem to be in UP in general. We also explore the case where the reachability or intersection are tested on a subset of objects, and show that this hardens complexity of the problems: both problems become NP-complete, and even Π^p₂-complete if we further require universality of the intersection. We next consider the exact cycle length problem, that is, determining whether there exists an initial configuration that yields a cycle in the configuration space having exactly a given length, and show that this problem is NP-complete. Lastly, we consider the t-predecessor and t-Garden of Eden problem, and prove that these are solvable in polynomial time even if the value of t is also given in binary as part of instance, and the two problems are in logarithmic space-uniform NC² if the value of t is given in unary as part of instance.
Cite as

Mitsunori Ogihara and Kei Uchizawa. Synchronous Boolean Finite Dynamical Systems on Directed Graphs over XOR Functions. In 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 170, pp. 76:1-76:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{ogihara_et_al:LIPIcs.MFCS.2020.76,
  author =	{Ogihara, Mitsunori and Uchizawa, Kei},
  title =	{{Synchronous Boolean Finite Dynamical Systems on Directed Graphs over XOR Functions}},
  booktitle =	{45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)},
  pages =	{76:1--76:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-159-7},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{170},
  editor =	{Esparza, Javier and Kr\'{a}l', Daniel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2020.76},
  URN =		{urn:nbn:de:0030-drops-127543},
  doi =		{10.4230/LIPIcs.MFCS.2020.76},
  annote =	{Keywords: Computational complexity, dynamical systems, Garden of Eden, predecessor, reachability}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2017.8
Generalized Predecessor Existence Problems for Boolean Finite Dynamical Systems

Authors: Akinori Kawachi, Mitsunori Ogihara, and Kei Uchizawa

Published in: LIPIcs, Volume 83, 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017)

Abstract
A Boolean Finite Synchronous Dynamical System (BFDS, for short) consists of a finite number of objects that each maintains a boolean state, where after individually receiving state assignments, the objects update their state with respect to object-specific time-independent boolean functions synchronously in discrete time steps. The present paper studies the computational complexity of determining, given a boolean finite synchronous dynamical system, a configuration, which is a boolean vector representing the states of the objects, and a positive integer t, whether there exists another configuration from which the given configuration can be reached in t steps. It was previously shown that this problem, which we call the t-Predecessor Problem, is NP-complete even for t = 1 if the update function of an object is either the conjunction of arbitrary fan-in or the disjunction of arbitrary fan-in. This paper studies the computational complexity of the t-Predecessor Problem for a variety of sets of permissible update functions as well as for polynomially bounded t. It also studies the t-Garden-Of-Eden Problem, a variant of the t-Predecessor Problem that asks whether a configuration has a t-predecessor, which itself has no predecessor. The paper obtains complexity theoretical characterizations of all but one of these problems.
Cite as

Akinori Kawachi, Mitsunori Ogihara, and Kei Uchizawa. Generalized Predecessor Existence Problems for Boolean Finite Dynamical Systems. In 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 83, pp. 8:1-8:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{kawachi_et_al:LIPIcs.MFCS.2017.8,
  author =	{Kawachi, Akinori and Ogihara, Mitsunori and Uchizawa, Kei},
  title =	{{Generalized Predecessor Existence Problems for Boolean Finite Dynamical Systems}},
  booktitle =	{42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017)},
  pages =	{8:1--8:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-046-0},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{83},
  editor =	{Larsen, Kim G. and Bodlaender, Hans L. and Raskin, Jean-Francois},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2017.8},
  URN =		{urn:nbn:de:0030-drops-81078},
  doi =		{10.4230/LIPIcs.MFCS.2017.8},
  annote =	{Keywords: Computational complexity, dynamical systems, Garden of Eden, predecessor}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact