IMSc Webinar

New Algorithmic Results using Noncommutative Algebraic Complexity

Abhranil Chatterjee

IMSc

Webinar: join at https://zoom.us/j/97583979049?pwd=bmsxUEE1bUh5S0dnUk5tR01nRTNDZz09 In this talk, we explore noncommutative algebraic computation from an algorithmic perspective, presenting new algorithmic results using algebraic complexity theory tools, especially noncommutative computation. We consider the following results: 1. We study the invertibility and span of the image set of noncommutative polynomials, an algorithmic version of a special class of Amitsur's theorem and the Bre\v{s}ar-Klep theorem. We also discuss a deterministic subexponential-time RIT algorithm for ABPs with inverses, a subclass of rational expressions of inversion height one. 2. We then study the image of noncommutative polynomials in a more general setting where we allow variables and their inverses to compute a free group algebra expression and show a randomized polynomial-time algorithm for polynomial-degree or exponential-sparsity case. 3. We show an efficient algorithm to compute the Hadamard product of two commutative polynomials. It yields a faster algorithm for multilinear monomial counting problem beating the brute-force, answering a question asked by Koutis and Williams. We also obtain a faster space-efficient algorithm for the decision version. 4. We study the rank upper bound of Nisan's matrix for the noncommutative rectangular permanent polynomial, noncommutative determinant polynomial, and some related polynomials to design explicit ABPs. We also show the hardness of computing the rectangular determinant. Based on joint work with V. Arvind, Rajit Datta, and Partha Mukhopadhyay.