Fine-grained complexity is a bridge between classical complexity and classical algorithms. Classical complexity seeks to classify problems as being members of complexity classes like P, NP, PSPACE, etc. These are coarse metrics that do not distinguish between problems solvable in time n, n^2, n^3 and n^10. On most computational models (RAM, Turing machine, etc.) there are time hierarchy theorems; there exist problems solvable in t(n) time which are not solvable in time t(n)^(1-epsilon) for all epsilon>0. Fine-grained complexity seeks to classify specific problems as being in a given level of the hierarchy. For example, showing a O(n^2) algorithm exists for a problem and proving a lower bound for that problem showing it must take n^(2-o(1)) time to solve. We lack the tools to do this unconditionally, so instead, we build networks of reductions showing equivalences between problems or conditional hardness of problems.
If you would like to contact us about our work, please scroll down to the people section and click on one of the group leads' people pages, where you can reach out to them directly.