Building above read-once polynomials: Identity testing and hardness of representation

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: 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 0-justified alternation-depth-3 ROPs. © 2014 Springer International Publishing Switzerland.