Max-Planck-Institut für Informatik
max planck institut
mpii logo Minerva of the Max Planck Society

MPI-INF or MPI-SWS or Local Campus Event Calendar

<< Previous Entry Next Entry >> New Event Entry Edit this Entry Login to DB (to update, delete)
What and Who
Title:Fine-Grained Complexity: Hardness for a Big Data World
Speaker:Karl Bringmann
coming from:Max-Planck-Institut für Informatik - D1
Speakers Bio:
Event Type:Joint Lecture Series
Visibility:D1, D2, D3, D4, D5, SWS, RG1, MMCI
We use this to send out email in the morning.
Level:Public Audience
Date, Time and Location
Date:Wednesday, 8 November 2017
Duration:60 Minutes
Building:E1 5
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.
Name(s):Jennifer Müller
EMail:--email address not disclosed on the web
Video Broadcast
Video Broadcast:NoTo Location:
Tags, Category, Keywords and additional notes
Attachments, File(s):
Jennifer Müller/MPI-INF, 08/24/2017 12:26 PM
Last modified:
Uwe Brahm/MPII/DE, 11/08/2017 07:01 AM
  • Jennifer Müller, 08/24/2017 12:28 PM -- Created document.