AG 1, AG 2, AG 3, INET, AG 4, AG 5, SWS, RG1, MMCI   Info

Public Audience

English

60 Minutes

Saarbrücken

An ever-increasing amount of data to be analyzed raises novel challenges for the theory of computation. How can we prove computational difficulty of a seemingly simple task when facing enormous data sets? Developing such methods is essential for determining which problems can or cannot be solved at a large scale.

Fine-grained complexity theory in P provides corresponding methods by establishing tight connections between fundamental algorithmic problems. In particular, we show that many natural sequence comparison problems cannot be solved in truly subquadratic time, assuming a stronger version of the famous P ≠ NP conjecture. These results give rigorous insights into the challenges encountered, e.g., in the context of genome comparison, and even aid in developing novel efficient algorithms.

Despite such early successes, this young theory is still in its infancy: In particular, most of the current results establish connections between isolated algorithmic problems, rather than between classes of problems. Can we establish a more encompassing theory and turn the current problem-centric state of the art to a full-fledged structural complexity theory for large data sets? Towards this end, we discuss a quest for completeness and classification theorems (inspired by a finite-model-theoretic approach and the Dichotomy Theorem for constraint satisfaction problems), and present promising initial results.

Jennifer Müller

+49 681 9325 2900

--email hidden

Zoom

997 1565 5535

passcode not visible

logged in users only