max planck institut
informatik
mpii logo Minerva of the Max Planck Society

Philip Wellnitz

I was a post-doctoral researcher at the Max Planck Institute for Informatics until March 31, 2024. This is my old page. Check my ORCID page or my GitHub profile for more up-to-date information.

Research Interests

I am happy to collaborate on any level.


Selected Publications


The following lists contain only selected publications. Consult dblp for a more complete list of publications.

Approximate String Matching

"Optimal Algorithms for Bounded Weighted Edit Distance" [arXiv] [slides]

with Alejandro Cassis and Tomasz Kociumaka

We give an \tilde{O}(n + n^0.5 k^1.5) algorithm for computing the weighted edit distance k between two strings. We prove that our algorithm is optimal for n^0.5 ≤ k ≤ n under the APSP hypothesis.

"Faster Pattern Matching under Edit Distance" [arXiv]

with Panagiotis Charalampopoulos and Tomasz Kociumaka

We give an O(n + n/m k^3.5) algorithm for PM with edits. This is the first improvement of Cole and Hariharan's [CH'02] O(n + n/m k^4) algorithm for the problem.

Counting (Small) Patterns in Graphs

"Counting Small Induced Subgraphs with Edge-monotone Properties" [arXiv]

with Simon Döring and Dániel Marx

We show that for any (non-trivial) edge-monotone graph property Φ, counting all induced subgraphs of a graph that satisy Φ is #W[1]-hard. Further, for most natural edge-monotone properties, no significant improvement upon the brute-force algorithms is possible (unless ETH fails).

"Counting and Finding Homomorphisms is Universal for Parameterized Complexity Theory" [arXiv] [slides]

with Marc Roth

We show that any problem P in #W[1] (or W[1]) is equivalent to the problem of counting homomorphisms between graphs of graph classes H(P) and G(P).


Code



Recent Teaching



Short CV