Title: "The singularity of symbolic matrices"
Speaker: Avi Wigderson, IAS, Princeton
Abstract:
I will discuss a deterministic polynomial time algorithm for the following problem, equivalent to the word problem for non-commutative fields.
Given a symbolic matrix, whose entries are linear functions in a set of non-commuting variables, determine if
it is singular (over the free skew field).
In contrast its commutative cousin, which is the famous polynomial identity testing problem (PIT), the best previous algorithm for the non-commutative version required exponential time, even if randomness is allowed.
Interestingly, this algorithm also gives a factor-2 approximation to the rank of symbolic matrices in commuting variables.
This problem turns out to be quite unique in the number of mathematical areas it touches.
I will mention the connections to (commutative) invariant theory, quantum Information, optimization and approximation of the permanent, all of which play an important role in the algorithm and its analysis.
Joint work with Ankit Garg, Leonid Gurvits and Rafael Olivera