Fine-grained complexity
Adam Polak Bocconi University
Course Summary |
About the lecturer |
Location and schedule |
Fine-grained complexity goes beyond the simplistic distinction between polynomial time and NP-hard problems, and proves more refined conditional lower bounds on running times of algorithms for certain problems. Have you ever wondered if the simple quadratic time algorithm for Edit Distance, which you learned in an introductory lecture on dynamic programming, can be improved upon? Spoiler alert: No, it cannot... at least not unless the so-called Strong Exponential Time Hypothesis fails. In this course we will define key hypotheses of fine-grained complexity, and show numerous reductions – often between seemingly distant problems. The course will be research-oriented.
About the lecturer:Bio: Adam Polak works as an assistant professor in the Department of Computing Sciences at Bocconi University. His research interests include algorithms and fine-grained complexity. Prior to joining Bocconi, he worked in the Algorithms and Complexity Department at the Max Planck Institute for Informatics, in the theory group at EPFL, and in the theory group at MIT. He finished his PhD in fall 2019, in the theory group at Jagiellonian University, advised by Paweł Idziak.
Location and schedule:
|
|
|
||||||||||||||||