Skip to main navigation
Skip to Content
Computer Science
University of Toronto
U of T Portal
Student Support
Contact
About
Why Study CS at U of T
Career Options
History of DCS
Giving to DCS
Computer Science at UofT Mississauga
Computer Science at UofT Scarborough
Contact
Employment Opportunities for Faculty/Lecturers
How to Find Us
Undergraduate
Prospective Undergraduates
Current Undergraduates
Graduate
Prospective Graduate Students
Current Graduate Students
Research
Research Areas
Partner with us
People
Faculty
Staff
In Memoriam
Alumni and Friends
Honours & Awards
Women in Computer Science
Graduate Student Society
Undergraduate Student Union
Undergraduate Artificial Intelligence Group
Undergraduate Theory Group
News & Events
News
Events
@DCS Update
Alumni
Donate
You are viewing: >
Home
>
News & Events
>
Events
> Theory Seminar- Feb 17
About
Undergraduate
Graduate
Research
People
News & Events
Theory Seminar- Feb 17
Event date: Friday, February 17, 2012, at 11:10 AM
Location: WB130
Speaker: Josh Grochow, University of Chicago
Title: Matrix Lie Algebra Isomorphism and Geometric Complexity Theory
Abstact:
Testing whether two Lie algebras of matrices are isomorphic is a fundamental algorithmic problem in algebra with potential applications to several problems in complexity theory, such as matrix multiplication, formula size, and the Mulmuley--Sohoni Geometric Complexity Theory program, as well as problems in areas as diverse as differential equations, particle physics, and group theory. We start from the beginning, with the definition of Lie algebras, and through lots of examples will try to give a feel for what Lie algebras are and how they behave. We show that certain cases of Matrix Lie Algebra Isomorphism are equivalent to Graph Isomorphism, and that the problem can be viewed as a "non-abelian" generalization of the Linear Code Equivalence problem. We also show how to solve other cases in polynomial time, and then apply these algorithms towards a derandomization of a recent randomized algorithm of Kayal for testing when a function can be gotten from the determinant by a linear change of variables. We will also touch on how Matrix Lie Algebra Isomorphism fits into the larger Geometric Complexity Theory program. The talk will not require any prior background on Lie algebras.