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

Homepage

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

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 problems in the area of combinatorial pattern 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.

Publications

Combinatorial Pattern Matching

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

with Panagiotis Charalampopoulos and Tomasz Kociumaka

FOCS'20

"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. SODA'19

"Clique-Based Lower Bounds for Parsing Tree-Adjoining Grammars" [arXiv] [slides]

with Karl Bringmann

We provide a conditional lower bound based of the k-clique conjecture for the parsing problem of tree-adjoining grammers, thereby showing that the current algorithms are likely optimal. CPM'17

(Parametrized) Counting Complexity

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

with Marc Roth and Johannes Schmitt

FOCS'20

"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). SODA'20

"Counting Induced Subgraphs: An Algebraic Approach to #W[1]-hardness" [arXiv] [slides]

with Julian Dörfler, Marc Roth, and Johannes Schmitt

We show a complexity dichotomy for the problem of counting induced subgraphs of a graph satisfying a property Φ for properties Φ that are non-trivial on edge-transitive graphs with a prime-power number of edges. MFCS'19

"Counting Answers to Existential Questions" [arXiv]

with Holger Dell and Marc Roth

We study the problem of counting conjunctive queries in (relational) databases and identify 5 (complexity) classes to which an instance may belong; thus refining existing classification results. ICALP'19 (B)

Miscellenious

"Faster Minimization of Tardy Processing Time on a Single Machine" [arXiv]

with Karl Bringmann, Nick Fischer, Danny Hermelin, and Dvir Shabtay

ICALP'20 (A)

Code

Teaching

Short CV