ABSTRACT. In this talk, I will discuss recent research in the area of graph isomorphism testing and beyond. After giving an introduction to the graph isomorphism problem, I will present the novel "Isomorphic Priors" computational model (Dorfman, Döring, Herold, Nanongkai, Neuen, Spoerhase, Wu). Solving a graph problem in this model involves two phases: (i) The preprocessing phase quickly analyzes a sequence of "prior graphs" along with (previously computed) exact optimal solutions. (ii) Subsequently, given a new graph H, a fast query phase must either (a) output the exact optimal solution, or (b) correctly report that H is not isomorphic to any of the prior graphs. I will discuss both positive and negative results for this computational model, and present open research directions. After that, I will address relaxations of graph isomorphism to capture similarity between graphs. I will present a recent additive approximation algorithm for graph edit distance on graphs of bounded VC dimension (Dahan, Grohe, Neuen, Novotny), and discuss several open problems in the realm of parameterized complexity.

ABSTRACT. In social networks, individuals’ decisions are influenced by their local connections, leading to \emph{majority illusion}, where some perceive a local majority opinion that contradicts the global majority. This distortion, prevalent in binary choices such as voting or vaccination stances, can skew public perception, making its mitigation desirable. In our model, we view the network as a \red–\blue colored graph, where a vertex is under majority illusion if its neighborhood has a \red majority despite \blue being globally dominant, and anchoring means flipping selected \red vertices to \blue. Eliminating majority illusion necessitates structural edits to the graph representing the social network. Grandi et al.\ (AAAI 2023) studied edge additions/deletions to reduce illusion, but such changes disrupt natural connections, creating artificial links or removing genuine ones, which are visible and undesirable to users. Instead, we propose \emph{anchoring} vertices---discreetly changing the opinions of selected users (e.g., influencers)---to preserve the network’s structure and hide interventions, offering a practical alternative. Fioravantes et al.\ (AAMAS 2025) aimed to eliminate all illusions with minimum anchors, but this is often impractical. We consider a realistic setting with a budget limiting the number of anchors ($k$) and aim to maximize the number of users ($p$) freed from illusion. Formally, we introduce the 𝑘-ANCH-𝑝-MIE problem: determine whether there is a set $X \subseteq V$ of size at $k$ such that anchoring $X$ eliminates majority illusion for at least $p$ vertices. \textbf{Dichotomy.} We establish the dichotomy regarding the classical computational complexity of the problem: 𝑘-ANCH-𝑝-MIE is polynomial-time solvable for graphs with maximum degree $\Delta \leq 2$, but \NP-complete for $\Delta \geq 3$. \textbf{Tight Exact Algorithm.} We show that the 𝑘-ANCH-𝑝-MIE is \W[1]-hard when parameterized by $k+p$, even for bipartite graphs. Moreover, under the Exponential Time Hypothesis ($\ETH$), there is no $f(k,p)\cdot n^{o(k+\sqrt{p})}$-time algorithm where $n$ denote the number of vertices in the graph (for any computable function $f$), showing that the $n^{O(k)}$-time brute-force algorithm is asymptotically optimal. \textbf{Tight Approximation Results.} Finally, complementing our hardness results, for the natural maximization version of the problem--- where the goal is to anchor $k$ vertices to eliminate majority illusion from as many vertices as possible--- we establish a tight $(1-\frac{1}{e})$-approximation via a natural greedy algorithm matching the optimal threshold for submodular maximization. We also prove that this is essentially optimal: no polynomial-time algorithm, can achieve an $(1-\frac{1}{e}+\epsilon)$-approximation for any $\epsilon>0$ unless $\P=\NP$. Moreover, under \ETH, any algorithm achieving an $(1-\frac{1}{e}+\epsilon)$ approximation factor for any constant $\epsilon\in(0,1)$, must take runtime $\Omega_k(|S|^{k^{\Omega(1)}})$, where $S$ denote the set of vertices that can possibly be anchored in the input graph.

ABSTRACT. Pearl’s Causal Hierarchy (PCH) is a central framework for reasoning about probabilistic, interventional, and counterfactual statements, yet the satisfiability problem for PCH formulas is computationally intractable in almost all classical settings. We revisit this challenge through the lens of parameterized complexity and identify the first gateways to tractability. Our results include fixed-parameter and XP-algorithms for satisfiability in key probabilistic and counterfactual fragments, using parameters such as primal treewidth and the number of variables, together with matching hardness results that map the limits of tractability. Technically, we depart from the dynamic programming paradigm typically employed for treewidth-based algorithms and instead exploit structural characterizations of well-formed causal models, providing a new algorithmic toolkit for causal reasoning.

ABSTRACT. Every flow on a DAG can be decomposed into weighted paths. The Minimum Flow Decomposition (MFD) problem, which is strongly NP-hard, asks for a smallest set of weighted paths whose sum is equal to the flow. This problem is crucial in various fields, including transportation planning, network communication, and bioinformatics, which has driven the development of fast heuristic algorithms. In this talk, I will give an overview of current theoretical results of the problem, focusing on its relations to DAG parameters, such as minimum path covers, and its connections to structural theory of DAGs. I will also present algorithmic results and improvements on a practical ILP solver for MFD based on this theoretical work.

ABSTRACT. Explainable artificial intelligence (XAI) is widely regarded as a mainstay of trustworthy AI. Recent years have witnessed massive efforts towards delivering reliable XAI solutions. Most of these efforts are based on non-symbolic methods of AI, and will invariably produce erroneous results. Thus, even if the predictions of a machine learning model could somehow be trusted, the lack of reliable explanations would render those predictions unworthy of trust. This talk provides a brief introduction to the field of logic-based XAI, a rigorous alternative to the still widely-used but highly problematic non-symbolic methods. The talk will also briefly dissect some of the more problematic shortcomings of non-symbolic XAI.

ABSTRACT. While neural networks are the cornerstone of modern machine learning, our understanding of the computational complexity of training them remains far from complete. To address this gap, in this talk we will survey recent advancements in both the classical and parameterized complexity of Neural Network Training (NNT). Specifically, we will examine the computational task of finding a set of weights and biases that optimally matches given training data within a specified network architecture. Beyond classical models, the talk will also highlight recent NNT developments for graph neural networks and quantized neural networks.