Room 327

New Algorithmic Results using Noncommutative Algebraic Complexity

Abhranil Chatterjee

IIT, Bombay

The topic of this PhD thesis is a study noncommutative algebraic computation
from an algorithmic perspective. It presents new algorithmic results using
algebraic complexity theory tools, especially noncommutative computation.
The results of the thesis are summarized below:

1. A study of the invertibility and span of the image set of noncommutative
polynomials and an algorithmic version of a special class of Amitsur's theorem
and the Bre\v{s}ar-Klep theorem. A discussion on a deterministic
subexponential-time RIT algorithm for ABPs with inverses, a subclass of
rational expressions of inversion height one.

2. A study of the image of noncommutative polynomials in a more general
setting where variables and their inverses can compute a free group
algebra expression. A randomized polynomial-time algorithm for
polynomial-degree or exponential-sparsity case.

3. An efficient algorithm to compute the Hadamard product of two commutative
polynomials and a faster algorithm for multilinear monomial counting problems
beating the brute force, answering a question of Koutis and Williams. A faster
space-efficient algorithm for the decision version.

4. A study of the rank upper bound of Nisan's matrix in connection with the
noncommutative rectangular permanent polynomial, noncommutative
determinant polynomial, and some related polynomials to design explicit ABPs.
A hardness result for computing the rectangular determinant.
The topic of this PhD thesis is a study noncommutative algebraic computation
from an algorithmic perspective. It presents new algorithmic results using
algebraic complexity theory tools, especially noncommutative computation.
The results of the thesis are summarized below:

1. A study of the invertibility and span of the image set of noncommutative
polynomials and an algorithmic version of a special class of Amitsur's theorem
and the Bre\v{s}ar-Klep theorem. A discussion on a deterministic
subexponential-time RIT algorithm for ABPs with inverses, a subclass of
rational expressions of inversion height one.

2. A study of the image of noncommutative polynomials in a more general
setting where variables and their inverses can compute a free group
algebra expression. A randomized polynomial-time algorithm for
polynomial-degree or exponential-sparsity case.

3. An efficient algorithm to compute the Hadamard product of two commutative
polynomials and a faster algorithm for multilinear monomial counting problems
beating the brute force, answering a question of Koutis and Williams. A faster
space-efficient algorithm for the decision version.

4. A study of the rank upper bound of Nisan's matrix in connection with the
noncommutative rectangular permanent polynomial, noncommutative
determinant polynomial, and some related polynomials to design explicit ABPs.
A hardness result for computing the rectangular determinant.