MPI-INF Logo
Campus Event Calendar

Event Entry

What and Who

Fine-Grained Complexity: Hardness for a Big Data World

Karl Bringmann
MMCI
Joint Lecture Series
AG 1, AG 2, AG 3, AG 4, AG 5, SWS, RG1, MMCI  
Public Audience
English

Date, Time and Location

Wednesday, 8 November 2017
12:15
60 Minutes
E1 5
002
Saarbrücken

Abstract

For many computational problems 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 by providing conditional
lower bounds via fine-grained reductions from certain hard core
problems. For instance, it allowed 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.
In this talk we will further discuss applications to Edit Distance,
Subset Sum, and RNA Folding.

Contact

Jennifer Müller
2900
--email hidden
passcode not visible
logged in users only

Jennifer Müller, 08/24/2017 12:28 -- Created document.