Header menu link for other important links
X
Building Above Read-Once Polynomials: Identity Testing and Hardness of Representation
M. Mahajan, B.V.R. Rao,
Published in Springer New York LLC
2016
Volume: 76
   
Issue: 4
Pages: 890 - 909
Abstract
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)× ∏ × ROF. (2) Weak hardness of representation theorems for sums of powers of constant-free ROPs and for ROFs of the form ∑ × ∏ × ∑. (3) A partial characterization of multilinear monotone constant-free ROPs. © 2015, Springer Science+Business Media New York.
About the journal
JournalData powered by TypesetAlgorithmica
PublisherData powered by TypesetSpringer New York LLC
ISSN01784617