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.