2026-07-22T06:50:05Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:20157 2024-07-02T07:52:48Z ddc:004 open_access

A Multivariate to Bivariate Reduction for Noncommutative Rank and Related Results Arvind, Vikraman Joglekar, Pushkar S. noncommutative rank rational formulas identity testing parallel complexity 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 [Cohn, 1990; Cohn, 2006] 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Vikraman Arvind and Pushkar S. Joglekar 2024 Is Part Of LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2024.14 urn:nbn:de:0030-drops-201571 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.14 eng https://creativecommons.org/licenses/by/4.0/legalcode