Engles, Christian and Rao, B V Raghavendra and Sreenivasaiah, Karteek
(2017)
On Σ A Σ A Σ Circuits: The Role of Middle Σ Fan-in, Homogeneity and Bottom Degree.
In: International Symposium on Fundamentals of Computation Theory, 11-13 September 2017, Bordeaux, France.
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 Pt i=1 Q αi i , where Qi = Pri j=1 ` dij ij 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 Σ ∧ Σ [≤n] ∧ [≥21] Σ and Σ ∧ Σ [≤2 √n/1000] ∧ [≥ √n] Σ 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.
Actions (login required)
 |
View Item |
Altmetric
Altmetric