Deterministic polynomial identity testing in non commutative models
Ran Raz, Amir Shpilka · 2004
We give a deterministic polynomial time algorithm for polynomial identity testing in the following two cases: 1. Non Commutative Arithmetic Formulas: The algorithm gets as an input an arithmetic formula in the non-commuting variables x1,..., xn and determines whether or not the output of the formula is identically 0 (as a formal expression). 2. Pure Arithmetic Circuits: The algorithm gets as an input a pure set-multilinear arithmetic circuit (as defined by Nisan and Wigderson) in the variables x1,..., xn and determines whether or not the output of the circuit is identically 0 (as a formal expression). One application is a deterministic polynomial time identity testing for set-multilinear arithmetic circuits of depth 3. We also give a deterministic polynomial time identity testing algorithm for non-commutative algebraic branching programs as defined by Nisan. Finally, we observe an exponential lower bound for the size of pure set-multilinear arithmetic circuits for the permanent and for the determinant. (Only lower bounds for the depth of pure circuits were previously known). 1