Max Planck Institute for Informatics
Department 1: Algorithms and Complexity
Campus E1 4, Room 324
66123, Saarbrücken
Germany
Email:
wellnitzmpiinf.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.
"Faster Approximate Pattern Matching: A Unified Approach" [arXiv] FOCS'20 
"Few Matches or Almost Periodicity: Faster Pattern Matching with Mismatches in Compressed Texts" [slides] 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 SLPcompressed texts. SODA'19 
"CliqueBased Lower Bounds for Parsing TreeAdjoining Grammars" [arXiv] [slides] We provide a conditional lower bound based of the kclique conjecture for the parsing problem of treeadjoining grammers, thereby showing that the current algorithms are likely optimal. CPM'17 
"Counting Small Induced Subgraphs Satisfying Monotone Properties" [arXiv] FOCS'20 
"Counting and Finding Homomorphisms is Universal for Parameterized Complexity Theory" [arXiv] [slides] 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] We show a complexity dichotomy for the problem of counting induced subgraphs of a graph satisfying a property Φ for properties Φ that are nontrivial on edgetransitive graphs with a primepower number of edges. MFCS'19 
"Counting Answers to Existential Questions" [arXiv] 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) 
"Faster Minimization of Tardy Processing Time on a Single Machine" [arXiv] ICALP'20 (A) 
