We like to introduce you to some interesting papers of our chair, which were recently accepted to conferences.
The first two papers are from the IEEE Congress on Evolutionary Computation (CEC) taking place on June 8th until 12th, 2025, Hangzhou, China.
The paper "Discrete Evolutionary Algorithms for Optimizing Sphere" was written by Aishwarya Radhakrishnan and Timo Kötzing. They investigate the use of discrete algorithms, specifically (1+1) EA and Random Local Search (RLS), for continuous and mixed-binary black-box optimization problems. The results show that a self-adjusting RLS performs competitively with CMA-ES on standard benchmarks and can be extended to mixed-binary optimization.
In the paper "Algorithm Performance Comparison of the (1+1) EA with Heavy-Tailed Mutators" by Xiaoyue Sherry Li, Sam Baguley and Timo Kötzing we study variants of the (1+1) EA with heavy-tailed mutation for discrete optimization in integer spaces. By combining heavy-tailed and concentrated distributions for both dimension selection and step size, we develop two novel variants — singly and doubly heavy-tailed mutators — and analyze their behavior on several problems with different landscape characteristics.
To study diffusion processes such as infections, simplified models are theoretically analyzed that contain phenomena such as reinfections and temporal immunity. Resistance to deseases is normally modelled using a state of total immunity that is left after some random time. "Resistance is Futile: Gradually Declining Immunity Retains the Exponential Duration of Immunity-Free Diffusion" written by Nico Klodt, Marcus Pappik and Dr. Andreas Göbel was accepted to the International Joint Conference on Artificial Intelligence (IJCAI) which will be held in Montreal, Canada from August 16th until August 22nd, studies the impact of replacing this state by an immunity that declines continuously.
"Chromatic Index under Parameterized Settings" investigates the parameterized complexity of the Chromatic Index problem, which asks whether the chromatic index of a graph equals its maximum degree. We provide an FPT algorithm for the problem parameterized by treewidth and kernelization results for structural parameters such as treewidth, feedback vertex set, cluster vertex deletion, and clique number. This paper was written by Dr. Shaily Verma and her collegues from India. It was accepted to 51st International Workshop on Graph-Theoretic Concepts in Computer Science, from June 11th until 13th at Europäische Akademie Otzenhausen, Germany.
The paper "Parameterised Holant Problems" was written by Panagiotis Aivasiliotis and Dr. Andreas Göbel together with Marc Roth (Queen Mary University of London) and Johannes Schmitt (ETH Zurich). The paper fully classifies the complexity of parameterised holant problems for families of symmetric signatures. The parameterised holant framework, introduced by Curticapean in 2015 constitutes an extensive family of coloured and weighted counting constraint satisfaction problems on graph-like structures, encoding as special cases various well-studied counting problems in parameterised and fine-grained complexity theory such as counting edge-colourful k-matchings, graph-factors, Eulerian orientations or, more generally, subgraphs with weighted degree constraints. We also study a natural uncoloured version of the (colourful) parameterised holant problem, which encodes as special cases the non-coloured analogues of the aforementioned examples. We establish a complete classification and in fact, our analysis reveals that the classification is different compared to the colourful setting, in the sense that we have less fixed-parameter tractable cases. With our results in hand, we are able to completely classify the complexity of Counting Factors of size k, to establish tight lower bounds for Modular Counting of (Colorful) Matchings and Counting Weight-???? Solutions to Systems of Linear Equations) as well as provide a new algorithm for the colourful variant of the former problem. It was accepted for the 52nd EATCS International Colloquium on Automata, Languages, and Programming (ICALP)and will be held in Aarhus, Denmark, from July 8th until 11th.
In the paper "Testing Thresholds and Spectral Properties of High-Dimensional Random Toroidal Graphs via Edgeworth-Style Expansions" Leon Schiller, Marcus Pappik and Dr. Andreas Göbel answer the question for which dimensions d it is possible to test whether a given random graph is a Random Geometric Graphs sampled on the d-dimensional torus under some L_p norm, or a standard Erdős–Rényi graph with independent edges, and we further tightly characterize the spectral properties of these models. We achieve this by introducing a novel technique to quantify dependencies between edges based on a modified version of multivariate Edgeworth expansions. Conference on Learning Theory (COLT) will be held in Lyon, France, from June 30th until 4th of July.
The paper "Dynamic Network Discovery via Infection Tracing" introduces a novel approach for discovering the connections between individuals in a time-varying network by observing the spread of infection over time. It provides efficient algorithms and theoretical bounds that specifically address the challenges posed by the temporal nature of these networks. This publication is based on the first part of Ben Bals' masterthesis and was written together with his thesis supervisors Michelle Döring, Nicolas Klodt, and George Skretas. It will be presented at the IJCAI in Montreal, Canada, from August 16th until 22nd.
