max planck institut
mpii logo Minerva of the Max Planck Society


Philip Wellnitz

Max Planck Institute for Informatics
Department 1: Algorithms and Complexity
Campus E1 4, Room 324
66123, Saarbrücken


Currently, I'm a PhD student at the Max Planck Institute for Informatics. I am interested in designing (faster) algorithms and matching conditional lower bounds for problems that are solvable in polynomial time, and those that are (probably) not. In particular, I work on (approximate) string matching.. Further, I am interested in the (parametrized) counting complexity of problems such as counting how often a graph appears in another graph as an (induced) subgraph.

Selected Publications

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

Combinatorial Pattern Matching

"Faster Approximate Pattern Matching: A Unified Approach" [arXiv]

with Panagiotis Charalampopoulos and Tomasz Kociumaka

We tighten the structural insight from [BKW, SODA'19] and show a similar result for pattern matching with edits. Using the structural insight, we obtain faster algorithms for PM with mismatches and edits for the fully-compressed and other settings.

"Few Matches or Almost Periodicity: Faster Pattern Matching with Mismatches in Compressed Texts" [slides]

with Karl Bringmann and Marvin Künnemann

We provide both new structural insight for pattern matching with mismatches in general, as well as a new, faster algorithm for pattern matching with mismatches in SLP-compressed texts.

(Parametrized) Counting Complexity

"Counting Small Induced Subgraphs Satisfying Monotone Properties" [arXiv]

with Marc Roth and Johannes Schmitt

We show that for any (non-trivial) monotone graph property Φ, counting all induced subgraphs of a graph that satisy Φ is #W[1]-hard and 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).



Short CV