2026-07-20T05:25:43Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:2333 2024-03-06T10:33:19Z ddc:004 open_access

The Power of Depth 2 Circuits over Algebras Saha, Chandan Saptharishi, Ramprasad Saxena, Nitin Polynomial identity testing depth 3 circuits matrix algebras local rings We study the problem of polynomial identity testing (PIT) for depth $2$ arithmetic circuits over matrix algebra. We show that identity testing of depth $3$ ($\Sigma \Pi \Sigma$) arithmetic circuits over a field $\F$ is polynomial time equivalent to identity testing of depth $2$ ($\Pi \Sigma$) arithmetic circuits over $\mathsf{U}_2(\mathbb{F})$, the algebra of upper-triangular $2\times 2$ matrices with entries from $\F$. Such a connection is a bit surprising since we also show that, as computational models, $\Pi \Sigma$ circuits over $\mathsf{U}_2(\mathbb{F})$ are strictly `weaker' than $\Sigma \Pi \Sigma$ circuits over $\mathbb{F}$. The equivalence further implies that PIT of $\Sigma \Pi \Sigma$ circuits reduces to PIT of width-$2$ commutative \emph{Algebraic Branching Programs}(ABP). Further, we give a deterministic polynomial time identity testing algorithm for a $\Pi \Sigma$ circuit of size $s$ over commutative algebras of dimension $O(\log s/\log\log s)$ over $\F$. Over commutative algebras of dimension $\poly(s)$, we show that identity testing of $\Pi \Sigma$ circuits is at least as hard as that of $\Sigma \Pi \Sigma$ circuits over $\mathbb{F}$. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Chandan Saha and Ramprasad Saptharishi and Nitin Saxena 2009 Is Part Of LIPIcs, Volume 4, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (2009) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.FSTTCS.2009.2333 urn:nbn:de:0030-drops-23334 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2009.2333 eng https://creativecommons.org/licenses/by-nc-nd/3.0/legalcode