ECCC-Report TR09-036https://eccc.weizmann.ac.il/report/2009/036Comments and Revisions published for TR09-036en-usMon, 04 May 2009 14:32:09 +0300
Paper TR09-036
| The Power of Depth 2 Circuits over Algebras |
Chandan Saha,
Ramprasad Saptharishi,
Nitin Saxena
https://eccc.weizmann.ac.il/report/2009/036We 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 U_2(F), the algebra of upper-
triangular 2 x 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 U_2(F) are strictly `weaker' than Sigma-Pi-Sigma
circuits over F. The equivalence further shows that PIT of depth 3
arithmetic circuits reduces to PIT of width-2 planar commutative
Algebraic Branching Programs (ABP). Thus, identity testing for
commutative ABPs is interesting even in the case of width-2.
Further, we give a deterministic polynomial time identity testing
algorithm for a Pi-Sigma circuit over any constant dimensional
commutative algebra over F. While over commutative algebras of
polynomial dimension, identity testing is at least as hard as that of
Sigma-Pi-Sigma circuits over F.
Mon, 04 May 2009 14:32:09 +0300https://eccc.weizmann.ac.il/report/2009/036