![Algorithms and Complexity in Algebraic Geometry_hi-res logo](/sites/default/files/styles/workshop_banner_sm_1x/public/2023-01/Algorithms%20and%20Complexity%20in%20Algebraic%20Geometry_hi-res.jpg?h=450de763&itok=r3pqykMn)
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.
All scheduled dates:
Upcoming
No Upcoming activities yet