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 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.