Joshua A. Grochow, Department of Computer Science, University of Colorado Boulder

Computational Complexity, Dynamical Systems, and Non-Convex Optimization

For a given computational problem, computational complexity asks the question of the resources needed - such as time, space, energy - by any algorithm which solves the problem. Despite algorithms being a form of discrete dynamical system (in both time & space), the theory of dynamical systems has unfortunately played little role in computational complexity to date. In this talk, I'll highlight several open questions in computational complexity, focusing on questions where analogies suggest that the methods of dynamical systems might be fruitfully applied. Along the way, we'll talk about the potential role in computational complexity of: coarse-graining / reduced-order modeling, condition number & robustness, and methods of comparing dynamical systems. My hope is that this will be the start of conversations around extending and leveraging the techniques of dynamical systems and non-convex optimization to better understand the nature of computation.