Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR26-274 | 29th September 2026 13:13

Rational Identity Testing for Noncommutative Circuits is in Polynomial Space

RSS-Feed




TR26-274
Authors: Vikraman Arvind, Pushkar Joglekar
Publication: 25th October 2026 07:51
Downloads: 9
Keywords: 


Abstract:

The rational identity testing problem, RIT, asks whether an input \emph{rational circuit}, i.e.\ a noncommutative arithmetic circuit that has inversion gates, computes the zero element of the free skew field. For rational \emph{formulas} the problem is known to be in deterministic polynomial time \cite{GGOW20}, \cite{IQS18}. For rational circuits of size $s$ the associated linear pencil has dimension $2^{O(s)}$, and the known algorithms use exponential time and exponential space.

We show in this note that RIT for rational circuits over $\Q$ and finite fields, including the question whether the circuit is a correct computation at every inversion gate, is decidable in deterministic space $O(s^{O(1)})$, and hence is in $\PSPACE$. As a consequence, noncommutative PIT for degree unrestricted input noncommutative circuits is also in $\PSPACE$. The proof depends on algorithms that take succinct representations of their input.
It has the following three observations that we put together to obtain the
$\PSPACE$ upper bound.

\begin{itemize}
\item Analyzing the Hrubes-Wigderson construction of a linear pencil for an input rational formula, we obtain a succinctly represented linear pencil $A$ of size $2^{O(s)}$ for the input rational \emph{circuit} of size $s$. More precisely, given indices $i$ and $j$ for the linear pencil we can compute $A_{i,j}$ in space polynomial in $s$ and length of $i,j$. This algorithm essentially gives a succinct presentation of the linear pencil $A$ obtained by the reduction.

\item By the recent theorem of Chatterjee, Ghosh, Gurjar, Raj and Thierauf that deciding whether or not a symbolic matrix $\sum_i A_ix_i$ has full noncommutative rank is in $\NC$. We note that their algorithm is
logspace-uniform $\NC$ and we use it as a black-box for computing rank of succinctly represented pencil $A$.

\item Finally, we note a folklore simulation which we state and prove in the form we need. If a problem is solved by a logspace-uniform family of \emph{deterministic} Boolean circuits of polylogarithmic depth, and its input is not written down but is presented by a polylogspace subroutine that returns any requested input bit, then the circuit can be evaluated in polylogarithmic space. Hence, simulating a depth $O(\log^{i}M)$ circuit for succinctly presented inputs of length $M = 2^{\Theta(s)}$ yields a polynomial space algorithm.
\end{itemize}



ISSN 1433-8092 | Imprint