A Fine-Grained Approach to Complexity
August 19, 2018, 2:00 PM - 2:50 PM
Location:
Corwin Pavilion West
University of California, Santa Barbara
Virginia Vassilevska Williams, Massachusetts Institute of Technology
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 current progress in this area, and will highlight some new developments and their relationship to cryptography.