Event Date: September 26, 2019 16:15
Fine-Grained Complexity Theory: Hardness for a Big Data World
Abstract - For many data analysis tasks we know some polynomial time algorithm, say in quadratic time, but it is open whether faster algorithms exist. In a big data world, it is essential to close this gap: If the true complexity of the problem is indeed quadratic, then it is intractable on data arising in areas such as DNA sequencing or social networks. On such data essentially only near-linear time algorithms are feasible. Unfortunately, classic hardness assumptions such as P!=NP are too coarse to explain the gap between linear and quadratic time.
Fine-grained complexity comes to the rescue: It provides conditional lower bounds via fine-grained reductions from certain hard core problems. For instance, it allows us to rule out truly subquadratic algorithms for the Longest Common Subsequence problem (used e.g. in the diff file comparison tool), assuming a certain strengthening of P!=NP. This talk is an introduction to fine-grained complexity theory with a focus on dynamic programming problems.
