Youming Qiao (University of Technology, Sydney)
Calvin Lab 116
On Symbolic Determinant Identity Test Problem
The symbolic determinant identity test (SDIT) problem asks whether the linear span of several square matrices contains a nonsingular matrix. A deterministic polynomial-time algorithm for this problem would imply strong circuit lower bounds. In this talk I will first describe an analogue between this problem and the perfect matching problem in bipartite graphs. This analogue connects SDIT to certain problems in invariant theory and algebraic geometry. Then I will introduce a useful tool to design deterministic algorithms for SDIT, namely the generalized Wong sequences, and exhibit its use when the linear space spanned by the given matrices have a basis consisting of rank-1 matrices.
Based on joint work with Gábor Ivanyos, Marek Karpinski, and Miklos Santha, arXiv 1307.6429.