Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR24-084 | 28th April 2024 10:05

A Multivariate to Bivariate Reduction for Noncommutative Rank and Related Results

RSS-Feed




Revision #1
Authors: Vikraman Arvind, Pushkar Joglekar
Accepted on: 28th April 2024 10:05
Downloads: 168
Keywords: 


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}


Paper:

TR24-084 | 24th April 2024 19:59

A Multivariate to Bivariate Reduction for Noncommutative Rank and Related Results





TR24-084
Authors: Vikraman Arvind, Pushkar Joglekar
Publication: 28th April 2024 09:16
Downloads: 151
Keywords: 


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}



ISSN 1433-8092 | Imprint