2004/11/13 by Ran Raz, A. Shpilka · 3 citations
Computer Science · Mathematics · #Bayesian Modeling and Causal Inference #Machine Learning and Algorithms #Formal Methods in Verification #Mathematics #Commutative property #Polynomial #Identity (music) #Discrete mathematics #Algebraic number #Multilinear map #Arithmetic circuit complexity #Exponential function #Arithmetic #Combinatorics #Pure mathematics #Arbitrary-precision arithmetic
paper · doi:10.1109/ccc.2004.1313845
openalex publication_date 2004/11/13 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/29
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 x/sub i/,...,x/sub n/ 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 arithmetic circuit (as defined by N. Nisan and A. Wigderson (1996)) in the variables x/sub i/,...,x/sub n/ and determines whether or not the output of the circuit is identically 0 (as a formal expression). We also give a deterministic polynomial time identity testing algorithm for non commutative algebraic branching programs as defined by N. Nisan (1991). One application is a deterministic polynomial time identity testing for multilinear arithmetic circuits of depth 3. Finally, we observe an exponential lower bound for the size of pure arithmetic circuits for the permanent and for the determinant. (Only lower bounds for the depth of pure circuits were previously known by N. Nisan and A. Wigderson (1996).