BIRS Workshop Lecture Videos

Banff International Research Station Logo

BIRS Workshop Lecture Videos

What can geometry tell us about theoretical computer science? Landsberg, J. M.


Complexity theory deals with determining when there does or does not exist a faster algorithm than the standard for some basic task such as multiplying matrices. In the case of matrix multiplication, Strassen shocked the world in 1969 by finding an algorithm faster than the standard one and computer scientists now make the astonishing conjecture that as the size of the matrices increase, it becomes almost as easy to multiply two nxn matrices as it is to add them. The famous P v. NP problem essentially conjectures that there is no fast solution to the traveling salesperson problem. Recently algebraic geometry and representation theory have led to advances regarding these conjectures. I will give an overview of these questions and the recent advances.

Item Media

Item Citations and Data


Attribution-NonCommercial-NoDerivatives 4.0 International