Computer Science/Discrete Mathematics Seminar II

The main object of study of this talk are matrices whose entries are linear forms in a set of formal variables (over some field). The main problem is determining if a given such matrix is invertible or singular (over the appropriate field of rational functions). As it happens, this problem has a dual life; when the underlying variables commute, and when they do not. Most of the talk will be devoted to explaining the many origins, motivations and interrelations of these two problems, in computational complexity, non-commutative algebra, (commutative) invariant theory, quantum information theory, optimization, approximating the permanent and more. I will provide an introduction to the relevant theory in each of these areas which will assume no prior knowledge. I will then describe a recent joint work with Garg, Gurvits and Olivera, giving a deterministic polynomial time algorithm for the non-commutative version (over the rationals), which uses many of the connections above. Strangely, while the problem is completely algebraic, the algorithm is analytic! This algorithm actually computes the non-commutative rank of the symbolic matrix, which turns out to give a factor-2 approximation to the commutative rank. This creates a different natural challenge for deterministic polynomial identity testing (PIT) - obtain a better approximation ratio for the rank.