Computer Science Theory Seminar
Youming Qiao
University of Technology Sydney
Matrix spaces as a linear algebraic analogue of graphs
Abstract: In the past few years, several research projects of mine (joint with collaborators) suggest that it is fruitful to view linear spaces of matrices as a linear algebraic analogue of graphs. In this talk I will propose such an analogue, and explain why such an analogue may make sense. I will then list several correspondences between structures on graphs and structures on matrix spaces. These include perfect matchings vs full-rank matrices, shrunk subsets vs shrunk spaces, independent sets vs isotropic spaces, random graphs vs random matrix spaces, and isomorphism concepts. These correspondences play an important role in the recent progress on non-commutative rational identity testing, form one bottleneck of putting graph isomorphism in P, and suggest a possible route for post-quantum cryptography.
Wednesday August 28, 2019 at 4:15 PM in 1325 SEO