Optimization, Complexity and Invariant Theory

Abstract: We show some results from (classical commutative) Polynomial Identity Testing in which the results or the technical ingredients of the noncommutative rank algorithm presented in the preceding talk play an important role. These include: computing nontrivial common block triangularizations of several matrices with an application in multivariate cruptography, some further problems from computational representation theory of finite groups and algebras, spaces spanned by rank one matrices, and a recent result of Bläser, Jindal and Pandey on approximating the commutative rank. We are also planning to mention some further special instances of PIT that are perhaps not hopeless to be derandomized or to be shown hard.