Wednesday, May 11 2022

11:30 - 13:00

11:30 - 13:00

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.

Done