Building Above Read-Once Polynomials: Identity Testing and Hardness of Representation
Building Above Read-Once Polynomials: Identity Testing and Hardness of Representation
复制标题
构建一次性多项式：身份测试和表示的硬度
DOI：
--
复制
发表时间：
2014
期刊：
影响因子：
1.1
通讯作者：
Karteek Sreenivasaiah
中科院分区：
文献类型：
--
作者：
M. Mahajan;B. V. Raghavendra Rao;Karteek Sreenivasaiah
Polynomial Identity Testing (PIT) algorithms have focussed 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: (1) a deterministic polynomial-time non-black-box PIT algorithm for ∑(2)×∏×ROFdocumentclass[12pt]{minimal} usepackage{amsmath} usepackage{wasysym} usepackage{amsfonts} usepackage{amssymb} usepackage{amsbsy} usepackage{mathrsfs} usepackage{upgreek} setlength{oddsidemargin}{-69pt} egin{document}$$sum ^{(2)} imes prod imes mathsf{ROF}$$end{document}. (2) Weak hardness of representation theorems for sums of powers of constant-free ROPs and for ROFdocumentclass[12pt]{minimal} usepackage{amsmath} usepackage{wasysym} usepackage{amsfonts} usepackage{amssymb} usepackage{amsbsy} usepackage{mathrsfs} usepackage{upgreek} setlength{oddsidemargin}{-69pt} egin{document}$$mathsf{ROF}$$end{document}s of the form ∑×∏×∑documentclass[12pt]{minimal} usepackage{amsmath} usepackage{wasysym} usepackage{amsfonts} usepackage{amssymb} usepackage{amsbsy} usepackage{mathrsfs} usepackage{upgreek} setlength{oddsidemargin}{-69pt} egin{document}$$sum imes prod imes sum $$end{document}. (3) A partial characterization of multilinear monotone constant-free ROPs.
Polynomial Identity Testing (PIT) algorithms have focussed 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: (1) a deterministic polynomial-time non-black-box PIT algorithm for ∑(2)×∏×ROFdocumentclass[12pt]{minimal} usepackage{amsmath} usepackage{wasysym} usepackage{amsfonts} usepackage{amssymb} usepackage{amsbsy} usepackage{mathrsfs} usepackage{upgreek} setlength{oddsidemargin}{-69pt} egin{document}$$sum ^{(2)} imes prod imes mathsf{ROF}$$end{document}. (2) Weak hardness of representation theorems for sums of powers of constant-free ROPs and for ROFdocumentclass[12pt]{minimal} usepackage{amsmath} usepackage{wasysym} usepackage{amsfonts} usepackage{amssymb} usepackage{amsbsy} usepackage{mathrsfs} usepackage{upgreek} setlength{oddsidemargin}{-69pt} egin{document}$$mathsf{ROF}$$end{document}s of the form ∑×∏×∑documentclass[12pt]{minimal} usepackage{amsmath} usepackage{wasysym} usepackage{amsfonts} usepackage{amssymb} usepackage{amsbsy} usepackage{mathrsfs} usepackage{upgreek} setlength{oddsidemargin}{-69pt} egin{document}$$sum imes prod imes sum $$end{document}. (3) A partial characterization of multilinear monotone constant-free ROPs.