On Σ A Σ A Σ Circuits: The Role of Middle Σ Fan-in, Homogeneity and Bottom Degree.

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.

[img]
Preview
Text
SPSPS.pdf

Download (395kB) | Preview

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.

[error in script]
IITH Creators:
IITH CreatorsORCiD
Sreenivasaiah, KarteekUNSPECIFIED
Item Type: Conference or Workshop Item (Paper)
Subjects: Computer science
Divisions: Department of Computer Science & Engineering
Depositing User: Team Library
Date Deposited: 16 May 2019 10:00
Last Modified: 16 May 2019 10:00
URI: http://raiithold.iith.ac.in/id/eprint/5199
Publisher URL: https://doi.org/10.1007/978-3-662-55751-8_19
Related URLs:

Actions (login required)

View Item View Item
Statistics for RAIITH ePrint 5199 Statistics for this ePrint Item