Fine-Grained Complexity and Algorithm Design

Fine-grained Complexity Theory is the design of reductions that prove running time lower bounds assuming a plausible complexity-theoretic conjecture such as the Strong Exponential Time Hypothesis. In this area the design of efficient algorithms goes hand in hand with proving fine-grained lower bounds: our goal is to prove matching upper and lower bounds, thus establishing best-possible algorithms, that achieve the optimal constant in the exponent of the running time. We apply this methodology to problems from various domains such as graphs, strings, geometry and optimization.