The chair has 4 new papers to announce.
In the paper "FO and MSO Model Checking on Temporal Graphs" Michelle Döring and Dr. George Skretas revisit the two known temporal analogues of Courcelles theorem which say that every computational problem that can be expressed in MSO logic can be solved in FPT time on graphs with bounded treewidth + lifetime or treewidth + temporal total degree. We show that there exists similar meta-theorems for the recently introduced purely temporal parameters vim and tim and provide new meta-theorems for all four parameters under FO logic on nowhere dense graphs (a broad class of graphs containing for example planar graphs). Lastly, we give an extensive collection of logical formulas expressing common graph problems studied on temporal graphs. This paper will be presented at The 5th Symposium on Algorithmic Foundations of Dynamic Networks (SANDS) on 1-3 July, 2026 in Le Havre, France.
The "Symmetric Parameterised Holants on Hypergraphs: Towards a Classification for Parameterised VCSPs" provides complete complexity classifications — both with respect to classical and parameterised complexity— for a family of parameterisedcounting constraint satisfaction problems (#CSPs)that is able to model problems that remained uncaptured by existing classifications for #CSPs, such as (weighted) parameterised factor problems on hypergraphs and counting weight-k solutions to systems of linear equations. In particular, our results are derived from establishing complete complexity classifications for parameterised holant problems on hypergraphs. The paper was written by Panagiotis Aivasiliotis and Dr. Andreas Göbel and will be presented at The 53rd EATCS International Colloquium on Automata, Languages, and Programming (ICALP) which will take place between 7–10 July, 2026 at Royal Holloway, University of London.
The paper "Robust Algorithms for Finding Cliques in Random Intersection Graphs via Sum-of-Squares" by Leon Schiller, Janosch Ruff and Dr. Andreas Göbel studies how to efficiently recover many overlapping hidden cliques (communities) in dense random graphs called random intersection graphs, which--in contrast to the case of non-overlapping communities--is a setting where standard spectral algorithms fail. The authors develop the first polynomial-time, robust algorithms that can exactly or approximately recover these overlapping communities even when the graph contains noise and adversarial edge corruptions. This is achieved using the sum-of-squares (SoS) proofs-to-algorithms framework enabled by suitable, efficiently verifiable certificates for the fact that any sufficiently large clique must almost entirely correspond to a real planted community.
The paper "Information-Theoretic Thresholds for Bipartite Latent-Space Graphs under Noisy Observations" by Leon Schiller, Marcus Pappik and Dr. Andreas Göbel studies the information-theoretic feasibility of detecting latent geometric structure in a noisy random graph where only a random subset of edges carries actual latent information. The authors derive almost tight, unconditional thresholds for when distinguishing this structured graph from pure noise is algorithmically possible, revealing that the problem is strictly easier when the set of edges carrying latent information is known in advance, compared to the case where this information is hidden. The main technical innovation that enables these results is a novel Fourier-theoretic framework that tracks subtle dependency patterns between edges, even across large subgraphs.
Both papers will be presented at The 39th Annual Conference on Learning Theory (COLT 2026) which takes place June 29-July 3 in San Diego, California.
