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

文章基本信息

  • 标题:Deterministic Identity Testing for Sum of Read Once ABPs
  • 本地全文:下载
  • 作者:Rohit Gurjar ; Arpita Korwar ; Nitin Saxena
  • 期刊名称:Electronic Colloquium on Computational Complexity
  • 印刷版ISSN:1433-8092
  • 出版年度:2014
  • 卷号:2014
  • 出版社:Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
  • 摘要:

    A read once ABP is an arithmetic branching program with each variable occurring in at most one layer. We give the first polynomial time whitebox identity test for a polynomial computed by a sum of constantly many ROABPs. We also give a corresponding blackbox algorithm with quasi-polynomial time complexity, i.e. n O ( log n ) . The motivating special case of this model is sum of constantly many set-multilinear depth- 3 circuits. The prior results for that model were only slightly better than brute-force (i.e. exponential-time).

  • 关键词:Basis isolation ; Evaluation dimension ; PIT ; Sum of ROABPs
国家哲学社会科学文献中心版权所有