[Colloquium] The role of symmetry (or the lack thereof) in algorithms and computational complexity

April 17, 2015 - Josh Grochow, Santa Fe Institute

Date: Tuesday, 4/21/15
Time: 11:00 AM - 12:15 PM
Place: Mechanical Engineering, Room 218

Speaker: Josh Grochow
Santa Fe Institute

Title: The role of symmetry (or the lack thereof) in algorithms and computational complexity

Abstract: Symmetry plays a fundamental role in many topics in computer science, from algorithms - the fast Fourier transform, vision, robotics, Gaussian elimination, matrix multiplication, and various graph algorithms - to coding theory, quantum computing, and lower bounds in computational complexity. Symmetry also plays a crucial role in the current attempt to separate P from NP, known as the Geometric Complexity Theory Program. Even in situations without symmetry, understanding the lack of symmetry can lead to useful insights. In this talk, I will discuss the role of symmetry in several of these areas of computer science, and speculate on future uses of symmetry in computer science and in science in general.

Bio: Joshua A. Grochow works on computational complexity, networks, and complex systems, using a variety of mathematical tools, from symmetry 
(group theory) to algebraic geometry. He is currently an Omidyar Fellow at the Santa Fe Institute, and was previously a postdoc at the University of Toronto. He received his Ph.D. from the University of Chicago, and also has a master's in computational biology from MIT.