Philip Wellnitz

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

Email: wellnitzmpi-inf.mpg.de

I am a post-doctoral researcher at the Max Planck Institute for Informatics.

Research Interests

Obtaining (provably) best-possible algorithms by designing faster algorithms and matching (conditional) lower bounds
(Approximate) String Matching and in general algorithms on strings
Counting Problems, also in parameterized settings (especially problems related to graph homomorphisms)

I am happy to collaborate on any level. In particular, if you happen to be interested in doing an internship or thesis with me, feel free to contact me with informal inquiries; you may want to mention one of my papers (see below) that you read and liked (so that I get an idea about the kind of problems you would like to work on). Note that any internship applications will still have to go through the general internship program that can be found here; also note that there are no spots left for Summer 2023 anymore.

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]

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 Satisfying Monotone Properties" [arXiv] [journal]

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).

Code

tikz-kneser: A tikz-library for drawing Kneser graphs.
SOSML: An interpreter for SML running in your browser, check it out at sosml.org. Alternatively, write your SML code in the text box below and click “interpret”.
Written at Saarland University together with Julian Baldus, Julian Dörfler, Jesko Dujmovic, Marvin Hofmann and Dominik Luche

val x = "Hello" ^ " "; x ^ "World!";
Code of other projects is available on my GitHub profile

Recent Teaching

Summer 2023
Lecturer: Techniques for Counting Problems (with Jacob Focke)
Winter 2022/23
Lecturer: Randomized Algorithms and Probabilistic Analysis of Algorithms
Winter 2021/22
Co-organizer: Reading Group Algorithms: Continuous Methods for Combinatorial Problems (with Kurt Mehlhorn, Roohani Sharma, and Hans Simon)

Short CV

October 2021 - present:
Postdoctoral scholar at the Max Planck Institute for Informatics
October 2018 - December 2021:
PhD student in Computer Science at Saarland University, Saarbrücken, Germany and the Max Planck Institute for Informatics
April 2017 - December 2021:
Member of the Saarbrücken Graduate School of Computer Science
B.Sc. in Computer Science at Saarland University, Saarbrücken, Germany
Abitur at Heinrich-Hertz-Gymnasium, Berlin, Germany