Fine-grained complexity of graph distance problemsSpeaker: Jenny
Title: Fine-grained complexity of graph distance problems
Date: 12 Nov 2020 17:30-18:45 EST (talk starts at 17:45)
Abstract: In classical complexity theory, all problems with polynomial-time algorithms are treated as more or less equivalently hard. Fine-grained complexity theory paints a more detailed picture of the complexity landscape, by distinguishing problems that can be solved in runtimes given by specific functions. I will discuss the fine-grained complexity of diameter approximation, a popular problem in this field, and present some cool reductions from k-SAT and k-OV giving conditional runtime lower bounds based on the Strong Exponential Time Hypothesis (SETH). I’ll also present a simple new “efficient” approximation algorithm for another graph distance parameter, called min-eccentricity.