2016/06/02 by V. Arvind, Partha Mukhopadhyay, Arvind, V. +3
Computer Science · #Complexity and Algorithms in Graphs #semigroups and automata theory #Cryptography and Data Security
paper · pdf · doi:10.48550/arxiv.1606.00596
In this paper we show that the black-box polynomial identity testing for noncommutative polynomials f∈\mathbbF⟨ z1,z2,⋯,zn ⟩ of degree D and sparsity t, can be done in randomized \poly(n,log t,log D) time. As a consequence, if the black-box contains a circuit C of size s computing f∈\mathbbF⟨ z1,z2,⋯,zn ⟩ which has at most t non-zero monomials, then the identity testing can be done by a randomized algorithm with running time polynomial in s and n and log t. This makes significant progress on a question that has been open for over ten years. The earlier result by Bogdanov and Wee [BW05], using the classical Amitsur-Levitski theorem, gives a randomized polynomial-time algorithm only for circuits of polynomially bounded syntactic degree. In our result, we place no restriction on the degree of the circuit. Our algorithm is based on automata-theoretic ideas introduced in [AMS08,AM08]. In those papers, the main idea was to construct deterministic finite automata that isolate a single monomial from the set of nonzero monomials of a polynomial f in \mathbbF⟨ z1,z2,⋯,zn ⟩. In the present paper, since we need to deal with exponential degree monomials, we carry out a different kind of monomial isolation using nondeterministic automata.