일시: 2025. 11. 24. (월요일), 오후 2시

장소: 제4공학관 D915호

Speaker: Aaron Sidford, Ph.D. (Associate Professor in the Departments of Management Science and Engineering and Computer Science at Stanford University)

Title: The Complexity of Solving Matrix Games

Abstract:
Matrix games are a fundamental class of bilinear optimization problems and perhaps some of the simplest non-trivial minimax optimization problems. Nevertheless, matrix games are pervasive and encompass well-studied, prominent algorithmic challenges including linear programming and finding a maximum-margin linear classifier. In this talk I will survey recent advances in understanding the complexity of approximately solving matrix games. In addition, this talk will introduce recent, new efficient algorithms for efficiently solving certain matrix games developed in joint work with Ishani Karmarkar and Liam O'Carroll.

Bio:
Aaron Sidford is an associate professor in the departments of Management Science and Engineering and Computer Science at Stanford University. He received his PhD from the Electrical Engineering and Computer Science Department at the Massachusetts Institute of Technology, where he was advised by Professor Jonathan Kelner. His research interests lie broadly in the design and analysis of algorithms, optimization theory, and the theory of computation with an emphasis on work at the intersection of continuous optimization, algorithmic graph theory, numerical linear algebra, and data structures. His work often focuses on the design of provably efficient algorithms for solving fundamental, large-scale optimization problems. He is the recipient of a Microsoft Research Faculty Fellowship, a Sloan Research Fellowship, an NSF CAREER Award, an ACM Doctoral Dissertation Award honorable mention, and best paper awards in COLT, FOCS, and SODA for work in these areas.