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

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: 1. A deterministic polynomial-time non-black-box PIT algorithm for∑(2) · ∏ ·ROF. 2. Weak hardness of representation theorems for sums of powers o