Department Colloquium - Joshua A. Grochow

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.

Friday, March 16, 2018 at 3:00pm to 4:00pm

Engineering Center, ECCR 265
1111 Engineering Drive, Boulder, CO 80309

Event Type



Science & Technology, Research & Innovation


Students, Faculty, General Public, Postdoc

College, School & Unit

Engineering & Applied Science

Applied Mathematics
Add to Calendar