A Multivariate to Bivariate Reduction for Noncommutative Rank and Related Results
<|reference_start|>A Multivariate to Bivariate Reduction for Noncommutative Rank and Related Results: We study the noncommutative rank problem, ncRANK, of computing the rank of matrices with linear entries in $n$ noncommuting variables and the problem of 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 deterministic NC algorithms, we revisit their interrelationship from a parallel complexity point of view. We show the following results:   1. 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.   2. 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.<|reference_end|>
@article{arvind2024a,
    title={A Multivariate to Bivariate Reduction for Noncommutative Rank and
  Related Results},
    author={Vikraman Arvind and Pushkar S Joglekar},
    journal={arXiv preprint arXiv:2404.16382},
    year={2024},
    archivePrefix={arXiv},
    eprint={2404.16382},
    primaryClass={cs.CC}
}