首页    期刊浏览 2024年07月07日 星期日
登录注册

文章基本信息

  • 标题:Identity Testing and Lower Bounds for Read- k Oblivious Algebraic Branching Programs
  • 本地全文:下载
  • 作者:Matthew Anderson ; Michael Forbes ; Ramprasad Saptharishi
  • 期刊名称:Electronic Colloquium on Computational Complexity
  • 印刷版ISSN:1433-8092
  • 出版年度:2015
  • 卷号:2015
  • 出版社:Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
  • 摘要:

    Read- k oblivious algebraic branching programs are a natural generalization of the well-studied model of read-once oblivious algebraic branching program (ROABPs). In this work, we give an exponential lower bound of exp ( n k O ( k ) ) on the width of any read- k oblivious ABP computing some explicit multilinear polynomial f that is computed by a polynomial size depth- 3 circuit. We also study the polynomial identity testing (PIT) problem for this model and obtain a white-box subexponential-time PIT algorithm. The algorithm runs in time 2 O ( n 1 − 1 2 k − 1 ) and needs white box access only to know the order in which the variables appear in the ABP.

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