IMSc Webinar

A Special Case of Rational Identity Testing and the Brešar-Klep Theorem

Abhranil Chatterjee

IMSc

Webinar; Join at https://bluejeans.com/717071302. In this talk, I'll describe the rational identity testing (RIT) problem, an interesting algorithmic problem in arithmetic circuit complexity that got plenty of attention over the last few years. We consider the following special case of rational identity testing: Given a noncommutative algebraic branching program (ABP) as white-box, whose edge labels are linear forms or inverses of linear forms, we show a deterministic polynomial-time algorithm to decide if the rational function computed by it is equivalent to zero in the universal free skew field. Given black-box access to the ABP, we give a deterministic quasi-polynomial time algorithm for this problem. In the second part of the talk, we focus on the image of noncommutative polynomials and explore algorithmic versions of two theorems, namely, Amitsur's theorem [S.A Amitsur, 1966] and the Brešar Klep theorem [Brešar and Klep, 2008] when the input polynomial is given by an ABP. Our techniques are based on some algebraic automata theory combined with known techniques for noncommutative ABP identity testing [Ran Raz and Amir Shpilka, 2005; Michael A. Forbes and Amir Shpilka, 2013]. It is based on a joint work with V. Arvind, Rajit Datta and Partha Mukhopadhyay.