Open Collections

What can geometry tell us about theoretical computer science?

Banff International Research Station for Mathematical Innovation and Discovery

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.

Mathematics; Dynamical systems and ergodic theory; Ordinary differential equations; Dynamical systems

video/mp4

Author affiliation: Texas A & M University

2016-12-12

Attribution-NonCommercial-NoDerivatives 4.0 International

http://hdl.handle.net/2429/59967

Unreviewed

http://creativecommons.org/licenses/by-nc-nd/4.0/