For every $n,s \geq 1$, we construct a matrix tuple $(A_1,\ldots,A_n) \in \mathrm{M}_s(\mathbb{Z})^n$ in deterministic $\mathrm{poly}(n,s)$ time such that every noncommutative polynomial $$f \in \mathbb{C}\langle x_1,x_2,\ldots,x_n\rangle$$ of sparsity at most $s$ satisfies $f = 0$ if and only if $f(A_1,A_2,\ldots,A_n) = 0$. The bit complexity of the entries in the matrices $A_1, \ldots, A_n$ is $O(s\log n)$. This immediately gives a deterministic one-query black-box identity testing algorithm for these polynomials. This is done under the standard assumption that the black-box can be queried over matrix algebras.

In particular, a black-box randomized polynomial-time algorithm was known for sparse noncommutative polynomials of exponential degree [Arvind, Joglekar, Mukhopadhyay, and Raja, 19], but (to the best of our knowledge) no deterministic polynomial-time algorithm was known. Interestingly, in the commutative case, deterministic polynomial-time black-box algorithm for sparse high-degree polynomials is well known [Klivans, and Spielman, 01] and [Saxena, 09].

Fixed a citation for high degree sparse commutative PIT.

For every $n,s \geq 1$, we construct a matrix tuple $(A_1,\ldots,A_n) \in \mathrm{M}_s(\mathbb{Z})^n$ in deterministic $\mathrm{poly}(n,s)$ time such that every noncommutative polynomial $$f \in \mathbb{C}\langle x_1,x_2,\ldots,x_n\rangle$$ of sparsity at most $s$ satisfies $f = 0$ if and only if $f(A_1,A_2,\ldots,A_n) = 0$. The bit complexity of the entries in the matrices $A_1, \ldots, A_n$ is $O(s\log n)$. This immediately gives a deterministic one-query black-box identity testing algorithm for these polynomials. This is done under the standard assumption that the black-box can be queried over matrix algebras.

In particular, a black-box randomized polynomial-time algorithm was known for sparse noncommutative polynomials of exponential degree [Arvind, Joglekar, Mukhopadhyay, and Raja, 19], but (to the best of our knowledge) no deterministic polynomial-time algorithm was known. Interestingly, in the commutative case, deterministic polynomial-time black-box algorithm for sparse high-degree polynomials is well known [Saxena, 09].