New Algorithmic results using Noncommutative Algebraic Complexity[HBNI Th210]

Abstract

Algebraic Complexity is the study of the complexity of computing multivariate polynomials where the complexity of a polynomial is the number of arithmetic operations such as additions, and multiplications required to compute it. The broad goal of this thesis is to explore the power of noncommutative computation, a subarea of algebraic complexity. We present new algorithmic results using tools and techniques from noncommutative algebraic complexity in this thesis. In the first part of the thesis, we focus on the image of noncommutative polynomials in various general settings. We explore the algorithmic questions centered around the invertibility and the trace of the image of a noncommutative polynomial. We show that we can leverage ideas from algebraic automata theory to answer these questions. We also study the image of free group algebra functions. It is a generalization of noncommutative polynomials where we allow noncommuting variables as well as their inverses as inputs. We obtain efficient identity testing algorithms for such functions. The second part of the thesis shows new algorithmic and arithmetic circuit upper bound results, mainly in the context of parameterized complexity, that utilizes new ideas from the noncommutative computation. We address two well-studied algorithmic problems in this area, multilinear monomial detection, and multilinear monomial counting, and show their connection to the computation of noncommutative Hadamard product. This connection leads to a new approach alled symmetrization that yields faster algorithms for these problems. Finally, we study new upper bound results for the noncommutative rectangular permanent, the noncommutative rectangular determinant, and some related polynomials. It complements the rank-based lower bound results for the corresponding polynomials.

Overall this thesis makes some progress in our understanding of the power of noncommutative algebraic complexity