Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > NONCOMMUTATIVE RANK:
Reports tagged with noncommutative rank:
TR24-084 | 24th April 2024
Vikraman Arvind, Pushkar Joglekar

A Multivariate to Bivariate Reduction for Noncommutative Rank and Related Results

Revisions: 1

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.

... more >>>


TR26-274 | 29th September 2026
Vikraman Arvind, Pushkar Joglekar

Rational Identity Testing for Noncommutative Circuits is in Polynomial Space

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 ... more >>>




ISSN 1433-8092 | Imprint