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 Verlag
2014
Volume: 8591 LNCS
   
Pages: 1 - 12
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 of constant-free ROPs and for 0-justified alternation-depth-3 ROPs. © 2014 Springer International Publishing Switzerland.