A Fine-Grained Approach to Algorithms and Complexity

Algorithmic research aims to determine the optimal worst case running time for computational problems of interest. Time hierarchy theorems from complexity theory state that there are problems that, on inputs of size n, can be solved in t(n) time but not in O(t(n)1-ε ) time for ε>0. The main challenge is to determine where in the time hierarchy implied by the time hierarchy theorems various specific natural and important problems lie. Decades of algorithms research have culminated in an impressive toolbox of sophisticated techniques that have been applied to obtain fast algorithms for many problems. Nevertheless, for many other central problems, the best known running times are essentially those of their classical, often brute-force algorithms from the 1950s and 1960s.