Computer Science Class of '60s Speaker - Chris Umans '96

Thursday, April 26 @ 8:00pm; Wege Auditorium (TCL 123)

“Algorithmic Magic: Behind the Scenes of Modern Computer Science”

Algorithmic advances have been responsible for some of the most remarkable applications of computation today, from search engines to machine learning to error-correcting codes, cryptography and scientific computing. Yet, even now, some of the most basic algorithmic questions remain unanswered, and among these are open problems with far-reaching implications for computer security and beyond.

In this talk, I will describe how computer scientists identify and abstract these key problems from a diversity of computing applications, and how some of these puzzles encapsulate deep questions about the nature of computation itself.

I’ll illustrate how computer scientists come up with fast algorithms, and what sorts of ideas are used, by focusing on the prominent problem of multiplying matrices. Many researchers have contributed to a decades-long race to find an optimal algorithm for this problem, which lies at the core of many applications. I’ll describe the surprising and clever ideas in play, and a promising new approach developed by myself and collaborators, that may have a chance to finally yield an optimal algorithm. No mathematical background will be assumed.

Dr. Umans received his undergraduate degree in Computer Science and Mathematics from Williams College and his Ph.D. in Computer Science from Berkeley in 2000. After spending two years as a postdoc in the Theory Group at Microsoft Research, he joined the Computer Science faculty at Caltech in 2002, where he is currently Professor of Computer Science. His research interests are in theoretical computer science, especially computational complexity, randomness in computation, and algebraic complexity and algorithms. He serves as an editor of the Journal of Computer and System Sciences, Algorithmica, Computational Complexity, ACM Transactions on Computation Theory, and Theory of Computing. He is a member of the scientific board of the Electronic Colloquium on Computational Complexity and the moderator for the Computational Complexity section of the arXiv. Dr. Umans is the recipient of an NSF CAREER award, an Alfred P. Sloan Research Fellowship, and a Simons Foundation Investigator award, as well as several best-paper and teaching awards.