[07-27] SKLCS seminar on "Counting (with) homomorphisms"

Title:      Counting (with) homomorphisms    

Speaker:    Prof.Radu Curticapean, University of Regensburg     

Time:     2026年7月27日（星期一）下午3:00-4:00    

Venue:    中国科学院软件研究所 5号楼337会议室    

Abstract:      In this talk, we survey results and techniques in parameterized and fine-grained counting complexity. Given a large n-vertex graph G, how hard is it to count small k-vertex patterns H in G? We can certainly use brute force in time O(n^k), but are substantially faster algorithms possible? Can we classify the complexity depending on the patterns being counted? As it turns out, many pattern counting problems admit a well-defined notion of basis change. We will study such basis changes and understand how they can be used to pinpoint the complexity of pattern counting problems, and we will discuss recent developments that allow us to turn parameterized reductions into polynomial-time reductions.    

Bio:     Radu Curticapean received his PhD in 2015 from Saarland University (Saarbrücken, Germany). His thesis on parameterized counting complexity received an award from the EATCS. He then worked as a post-doc at the Hungarian Academy of Sciences (Budapest, Hungary), as a research fellow at the Simons Institute for the Theory of Computing (Berkeley, USA), and as a post-doc, assistant professor, and associate professor at the IT University of Copenhagen (Copenhagen, Denmark), before joining the University of Regensburg (Regensburg, Germany) as a full professor and leader of the Algorithms and Complexity group.

His research focuses on counting problems and algebraic complexity theory, and he currently is the PI of the ERC Starting Grant project "Counting (with) homomorphisms", which explores fascinating connections between the theory of homomorphism counts and problems in algorithms, complexity, and algebra.