首页    期刊浏览 2024年12月02日 星期一
登录注册

文章基本信息

  • 标题:Building above read-once polynomials: identity testing and hardness of representation
  • 本地全文:下载
  • 作者:Meena Mahajan ; Raghavendra Rao B V ; Karteek Sreenivasaiah
  • 期刊名称:Electronic Colloquium on Computational Complexity
  • 印刷版ISSN:1433-8092
  • 出版年度:2015
  • 卷号:2015
  • 出版社:Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
  • 摘要:

    Polynomial Identity Testing (PIT) algorithms have focused on polynomials computed either by small alternation-depth arithmetic circuits, or by read-restricted formulas. Read-once polynomials (ROPs) are computed by read-once formulas (ROFs) and are the simplest of read-restricted polynomials. Building structures above these, we show the following: \begin{enumerate} \item A deterministic polynomial-time non-black-box PIT algorithm for (2) RO F . \item Weak hardness of representation theorems for sums of powers of constant-free ROPs and for ROPs of the form . \item A partial characterization of multilinear monotone constant-free ROPs. \end{enumerate}

  • 关键词:arithmetic circuits ; Polynomial Itdentity Testing
国家哲学社会科学文献中心版权所有