Can we understand big systems from their small parts?

ABSTRACT: Complex systems are those in which many components combine their local behavior to produce unexpected, emergent global behavior. Examples range from natural systems such as brains, organisms, and ecosystems, to engineered systems such as cities, transportation networks, and computers. Frequently such systems are too large to study as a whole, so we instead study them by examining their many small sub-systems, and trying to understand how those sub-systems fit together. In this talk we will discuss two different models of the underlying static structure of many complex systems: graphs and tensors. What can we learn about these objects by looking at their small sub-parts, and how can we extract that information algorithmically? Both of these turn out to be related to classical questions in mathematics and central questions in computational complexity, such as the complexity of Graph Isomorphism and P versus NP. 

BIO: Joshua A. Grochow is an assistant professor of computer science and mathematics at CU Boulder. His work focuses on two deeply - but not obviously - related themes: 1) understanding the ultimate limits of computation (computational complexity), especially in their two-way relationship with algebraic geometry, representation theory, and group theory, and 2) developing the theory of complex systems and complex networks. Prior to his current position, he was an Omidyar Fellow at the Santa Fe Institute and a postdoc in the CS Theory group at the University of Toronto. He got his PhD in CS from the University of Chicago, an MEng in CS focusing on computational biology from the Massachusetts Institute of Technology, and undergraduate degrees in CS and mathematics from MIT.