Complexity Monotonicity of Pattern Counting Problems
Date: 18 November 2021
Place: Room 5016 (5th floor, Lab LM). Badge required for in-person attendance. Admittance not allowed if max capacity is exceeded.
Speaker: Marc Roth (University of Oxford)
Abstract: In this talk, I will present recent results on the complexity of pattern counting problems from the perspective of parameterized and fine-grained complexity theory. In particular, I will introduce and discuss "Complexity Monotonicity", a novel and powerful tool due to Curticapean, Dell and Marx, which provides a unifying view on problems that require to count small structures in large networks, subsuming graph homomorphisms, embeddings and induced subgraphs. Talk based on the following works: Curticapean, Dell and Marx (STOC '17); R, Schmitt (IPEC '18); R, Schmitt, and Wellnitz (FOCS '20); Bressan, R (FOCS '21).
Bio Sketch: Marc Roth is Senior Research Associate in Algorithms and Complexity Theory at the Department of Computer Science at the University of Oxford. His research concerns computational counting problems, and in particular the multivariate and exact complexity of counting problems that are infeasible from a classical point of view.
Persona di riferimento: Marco Bressan