__
Revision #1 to TR24-084 | 28th April 2024 10:05
__
#### A Multivariate to Bivariate Reduction for Noncommutative Rank and Related Results

**Abstract:**
We study the \emph{noncommutative rank} problem, $\NCRANK$, of computing the rank of matrices with linear entries in $n$ noncommuting variables and the problem of \emph{noncommutative Rational Identity Testing}, $\RIT$, which is to decide if a given rational formula in $n$ noncommuting variables is zero on its domain of definition.

Motivated by the question whether these problems have \emph{deterministic} $\NC$ algorithms, we revisit their interrelationship from a parallel complexity point of view.

We show the following results:

\begin{enumerate}

\item Based on Cohn's embedding theorem \cite{Co90,Cohnfir} we show deterministic $\NC$ reductions from multivariate $\NCRANK$ to bivariate $\NCRANK$ and from multivariate $\RIT$

to bivariate $\RIT$.

\item We obtain a deterministic $\NC$-Turing reduction from bivariate $\RIT$ to bivariate $\NCRANK$, thereby proving that a deterministic $\NC$ algorithm for bivariate $\NCRANK$ would imply that both multivariate $\RIT$ and multivariate $\NCRANK$ are in deterministic $\NC$.

\end{enumerate}

__
TR24-084 | 24th April 2024 19:59
__

#### A Multivariate to Bivariate Reduction for Noncommutative Rank and Related Results

**Abstract:**
We study the \emph{noncommutative rank} problem, $\NCRANK$, of computing the rank of matrices with linear entries in $n$ noncommuting variables and the problem of \emph{noncommutative Rational Identity Testing}, $\RIT$, which is to decide if a given rational formula in $n$ noncommuting variables is zero on its domain of definition.

Motivated by the question whether these problems have \emph{deterministic} $\NC$ algorithms, we revisit their interrelationship from a parallel complexity point of view.

We show the following results:

\begin{enumerate}

\item Based on Cohn's embedding theorem \cite{Co90,Cohnfir} we show deterministic $\NC$ reductions from multivariate $\NCRANK$ to bivariate $\NCRANK$ and from multivariate $\RIT$

to bivariate $\RIT$.

\item We obtain a deterministic $\NC$-Turing reduction from bivariate $\RIT$ to bivariate $\NCRANK$, thereby proving that a deterministic $\NC$ algorithm for bivariate $\NCRANK$ would imply that both multivariate $\RIT$ and multivariate $\NCRANK$ are in deterministic $\NC$.

\end{enumerate}