Header menu link for other important links
X
On Σ ∧ Σ ∧ Σ circuits: The role of middle Σ fan-in, homogeneity and bottom degree
Published in Springer Verlag
2017
Volume: 10472 LNCS
   
Pages: 230 - 242
Abstract
We study polynomials computed by depth five Σ ∧ Σ ∧ Σ arithmetic circuits where ‘Σ’ and ‘∧’ represent gates that compute sum and power of their inputs respectively. Such circuits compute polynomials of the form (formula presented), where (formula presented) where ℓij are linear forms and ri, αi, t > 0. These circuits are a natural generalization of the well known class of Σ ∧ Σ circuits and received significant attention recently. We prove an exponential lower bound for the monomial x1 · · · xn against depth five (formula presented) and (formula presented) arithmetic circuits where the bottom Σ gate is homogeneous. Our results show that the fan-in of the middle Σ gates, the degree of the bottom powering gates and the homogeneity at the bottom Σ gates play a crucial role in the computational power of Σ ∧ Σ ∧ Σ circuits. © Springer-Verlag GmbH Germany 2017.
About the journal
JournalData powered by TypesetLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
PublisherData powered by TypesetSpringer Verlag
ISSN03029743
Open AccessYes
Concepts (8)
  •  related image
    Computation theory
  •  related image
    Logic circuits
  •  related image
    Timing circuits
  •  related image
    Arithmetic circuit
  •  related image
    Computational power
  •  related image
    Lower bounds
  •  related image
    Natural generalization
  •  related image
    Electric network analysis