首页    期刊浏览 2024年11月30日 星期六
登录注册

文章基本信息

  • 标题:Identity Testing for +-Regular Noncommutative Arithmetic Circuits
  • 本地全文:下载
  • 作者:Vikraman Arvind ; Pushkar Joglekar ; Partha Mukhopadhyay
  • 期刊名称:Electronic Colloquium on Computational Complexity
  • 印刷版ISSN:1433-8092
  • 出版年度:2016
  • 卷号:2016
  • 出版社:Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
  • 摘要:

    An efficient randomized polynomial identity test for noncommutative polynomials given by noncommutative arithmetic circuits remains an open problem. The main bottleneck to applying known techniques is that a noncommutative circuit of size s can compute a polynomial of degree exponential in s with a double-exponential number of nonzero monomials. In this paper, which is a follow-up on our earlier article [AMR16], we report some progress by dealing with two natural subcases (both allow for polynomials of exponential degree and a double exponential number of monomials):

    (1) We consider \emph{ + -regular} noncommutative circuits: these are homogeneous noncommutative circuits with the additional property that all the + -gates are layered, and in each + -layer all gates have the same syntactic degree. We give a \emph{white-box} polynomial-time deterministic polynomial identity test for such circuits. Our algorithm combines some new structural results for + -regular circuits with known results for noncommutative ABP identity testing [RS05PIT], rank bound of commutative depth three identities [SS13], and equivalence testing problem for words [Loh15, MSU97, Pla94]. (2) Next, we consider noncommutative circuits: these are noncommutative circuits with layered + -gates such that there are only two layers of + -gates. These + -layers are the output + -gate and linear forms at the bottom layer; between the + -layers the circuit could have any number of gates. We given an efficient randomized \emph{black-box} identity testing problem for circuits. In particular, we show if f \F Z is a nonzero noncommutative polynomial computed by a circuit of size s , then f cannot be a polynomial identity for the matrix algebra M s ( F ) , where the field F is a sufficiently large extension of \F depending on the degree of f .

国家哲学社会科学文献中心版权所有