Alladi Ramakrishnan Hall

Trading Determinism for Noncommutativity in Edmonds' Problem

Abhranil Chatterjee

ISI Kolkata

In this talk, we will explore the following two algorithmic problems.

Let X be a set of variables partitioned into k many buckets such that the variables in each bucket are noncommuting but they commute across the buckets. Given as input a square matrix T whose entries are linear forms over X, we first consider the partially commutative Edmonds' problem that asks to decide if T is invertible or not (over the universal skew field of fractions of the partially commutative polynomial ring). We will present a deterministic polynomial-time algorithm for this problem for constant k. The special case k=1 is the noncommutative Edmonds' problem which admits a deterministic polynomial-time algorithm [Garg, Gurvits, Oliveira, and Wigderson (2016); Ivanyos, Qiao, Subrahmanyam (2018); Hamada and Hirai (2021)].

The other problem of our interest is the equivalence testing problem of two multi-tape weighted automata. Algebraically, the equivalence testing problem for the k-tape case reduces to testing whether a partially commutative rational series over a k-partitioned set X is zero or not [Worrell(2013)]. In this talk, we show a deterministic polynomial-time algorithm for this problem for constant k resolving a long-standing open problem [Harju and Karhumäki (1991), Worrell(2013)].

It is based on a joint work with V. Arvind and Partha Mukhopadhyay. The preliminary version (available at eccc.weizmann.ac.il/report/2024/073/) has been accepted at FOCS, 2024.