DLS: Virginia Vassilevska Williams on Breakthroughs in Algorithms & Complexity 📊

Bio: Virginia Vassilevska Williams is a Professor at MIT EECS and CSAIL. She obtained her Ph.D. from Carnegie Mellon University in 2008. After research and postdoctoral positions at the IAS in Princeton, UC Berkeley and Stanford, she spent 3.5 years as an assistant professor at Stanford University before joining MIT in early 2017. She is the recipient of an NSF CAREER award, a Google Faculty Research Award, an Alfred P. Sloan Research Fellowship, a 2023 Simons Investigator Award and a FOCS 2024 Test of Time Award. In 2018 she gave an invited lecture at the International Congress of Mathematicians. A central goal of algorithmic research is to determine how fast computational problems can be solved in the worst case. Unfortunately, for many central problems, the best known running times are essentially those of their classical algorithms from the 1950s and 1960s. For years, the main tool for explaining computational difficulty have been NP-hardness reductions, basing hardness on P ≠ NP. However, if one cares about exact running time (as opposed to merely polynomial vs non-polynomial), NP-hardness is not applicable, especially if the problem is already solvable in polynomial time. In recent years, a new theory has been developed, based on “fine-grained reductions” that focus on exact running times. In this talk I will give an overview of this area, and will highlight some new developments. This distinguished lecture is presented jointly by Women in Mathematics, Women in Computer Science and the Cheriton School of Computer Science. 🩷💛 Engage with us online! 🖤🩷 Instagram: https://instagram.com/waterloomath LinkedIn: https://www.linkedin.com/showcase/faculty-of-math/ Facebook: https://facebook.com/waterloomath -- As North America's only dedicated Faculty of Math, we are nationally and internationally recognized as one of the top schools for Mathematics and Computer Science. With nearly $30 million in research funding (2019/20) and an alumni network of over 45,000 across more than 100 countries, our students, faculty, and graduates continue to push the boundaries of research to discover new ways to harness the power of mathematics, computer science, and statistics. Visit our website at https://uwaterloo.ca/math/