Showing cs.CCShow all
2 papers · 1 filter
cs.CC2025
Black-Box Identity Testing of Noncommutative Rational Formulas in Deterministic Quasipolynomial Time
V. Arvind, Abhranil Chatterjee, Partha Mukhopadhyay
Rational Identity Testing (RIT) is the decision problem of determining whether or not a noncommutative rational formula computes zero in the free skew field. It admits a determinis…
cs.CC2024
Trading Determinism for Noncommutativity in Edmonds' Problem
V. Arvind, Abhranil Chatterjee, Partha Mukhopadhyay
Let be a partitioned set of variables such that the variables in each part are noncommuting but for any , the variables $x\in…