Header menu link for other important links
X
On Σ ∧ Σ ∧ Σ circuits: The role of middle Σ fan-in, homogeneity and bottom degree
C. Engels, B.V.R. Rao,
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.