Philip Wellnitz / フィリップ・ヴェルニッツ

〒101-8430
Tokyo-to Chiyoda-ku Hitotsubashi 2-1-2
National Institute of Informatics
Room 1616

Email: wellnitznii.ac.jp

I am an Assistant Professor at the National Institute of Informatics and The Graduate University for Advanced Studies in Tokyo, Japan. Before that, I was a post-doctoral researcher at the Max Planck Institute for Informatics, Saarbruecken, Germany. This is a makeshift temporary webpage that will be replaced soon.

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