Randomized polynomial time identity testing for noncommutative circuits

In this paper we show that black-box polynomial identity testing for noncommutative polynomials f ∈𝔽⟨ z 1 , z 2 ,…, z n ⟩ of degree D and sparsity t , can be done in randomized ( n ,log t ,log D ) time. As a consequence, given a circuit C of size s computing a polynomial f ∈𝔽⟨ z 1 , z 2 ,…, z n ⟩ with at most t non-zero monomials, then testing if f is identically zero 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. Our algorithm is based on automata-theoretic ideas that can efficiently isolate a monomial in the given polynomial. In particular, we carry out the monomial isolation using nondeterministic automata.

Authors

• Vikraman Arvind
• Pushkar S. Joglekar
• Partha Mukhopadhyay
• S. Raja 0001

Keywords

• Algebraic Complexity
• Randomized Algorithm
• Non-commutative Computation
• Polynomial Identity Testing