Panagiotis Aivasiliotis

Short CV

I am a second-year Phd student at the Chair of Algorithm Engineering at Hasso Plattner Institute. Before coming to HPI, I received a joint diploma (B.Sc. & M.Eng.) from the department of Electrical and Computer Engineering at National Technical University of Athens (Greece).

Research Interests

My current research is focused on the (counting) complexity classification of computing graph motif parameters. In a nutshell, a graph motif parameter maps a graph G to a combinatorial sum of homomorphism counts #Hom(F, G) for finitely many graphs F (that do not depend on G). The problem of evaluating a graph motif parameter applies to a wide range of well-studied problems including counting occurrences of (small) pattern graphs (e.g., triangles or cliques in general) in large graph networks, counting the number of answers to conjunctive queries and evaluating holants to name a few.

In particular, the problem of evaluating a graph motif parameter is more suitably studied within the parameterized world. For example, when counting answers to conjunctive queries, we may parametrize by the size of the query, which is reasonable considering that the database is typically much larger than the query itself. In this context, we are primarily interested in classifying the instances between those that are fixed-parameter tractable (FPT) and those that are #W[1]-hard. It is known that evaluating graph motif parameters when parameterized by the encoding of the coefficients always admits such a dichotomy (which is non-trivial since there exist intermediate problems). Thus, my task revolves around finding (explicit) dichotomy criteria, the study of which can lead to highly challenging combinatorial problems.