id: 06098242
dt: a
an: 06098242
au: Saha, Chandan; Saptharishi, Ramprasad; Saxena, Nitin
ti: The power of depth 2 circuits over algebras.
so: Kannan, Ravi (ed.) et al., IARCS annual conference on foundations of
    software technology and theoretical computer science (FSTTCS 2009),
    December 15‒17, 2009, Kanpur, India. Wadern: Schloss Dagstuhl ‒
    Leibniz Zentrum für Informatik (ISBN 978-3-939897-13-2). LIPICS ‒
    Leibniz International Proceedings in Informatics 4, 371-382, electronic
    only (2009).
py: 2009
pu: Wadern: Schloss Dagstuhl ‒ Leibniz Zentrum für Informatik
la: EN
cc: 
ut: polynomial identity testing; depth 3 circuits; matrix algebras; local rings
ci: 
li: doi:10.4230/LIPIcs.FSTTCS.2009.2333
    http://subs.emis.de/LIPIcs/frontdoor_e30d.html
ab: Summary: 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 (ΣΠΣ)$ arithmetic circuits over a field
    $\mathbb{F}$ is polynomial time equivalent to identity testing of depth
    $2 (ΠΣ)$ arithmetic circuits over $\mathsf{U}_2(\mathbb{F})$, the
    algebra of upper-triangular $2\times 2$ matrices with entries from
    $\mathbb{F}$. Such a connection is a bit surprising since we also show
    that, as computational models, $ΠΣ$ circuits over
    $\mathsf{U}_2(\mathbb{F})$ are strictly ‘weaker’ than $ΣΠΣ$
    circuits over $\mathbb{F}$. The equivalence further implies that PIT of
    $ΣΠΣ$ circuits reduces to PIT of width-2 commutative algebraic
    branching programs (ABP). Further, we give a deterministic polynomial
    time identity testing algorithm for a $ΠΣ$ circuit of size $s$ over
    commutative algebras of dimension $O(\log s/\log\log s)$ over
    $\mathbb{F}$. Over commutative algebras of dimension
    $\mathrm{poly}(s)$, we show that identity testing of $ΠΣ$ circuits is
    at least as hard as that of $ΣΠΣ$ circuits over $\mathbb{F}$.
rv: