"Sparse Cuts in Graphs"
Dieter Rautenbach, Ulm University
This talk surveys several recent results on sparse vertex cuts in graphs. We consider in particular independent cuts, forests cuts, cuts inducing subgraphs of bounded maximum degree or degeneracy, and sparse minimum cuts. While mostly bounds and structural results are presented, we also consider algorithmic aspects. The talk is based on joint work with S. Bessy, V. Chernyshev, T. Hartel, J. Rauch, L. Redina, and U.S. Souza.
Prof. Dr. Dieter Rautenbach
W3 Professor | Vice President for Career Development | Ulm University, Germany
Professor Dieter Rautenbach is a highly distinguished expert in Discrete Mathematics, Graph Theory, and Combinatorial Optimization. He holds a W3 Professorship at Ulm University and serves as Vice President for Career Development, combining internationally recognized research excellence with senior academic leadership.
With a research career spanning more than 25 years, Professor Rautenbach has authored over 190 peer-reviewed publications, delivering fundamental contributions to central areas of graph theory including domination, matchings, cycles, and graph convexity. His work is widely cited and continues to shape both theoretical advances and emerging directions in discrete mathematics.
Professor Rautenbach is a prominent international scientific leader and sought-after keynote speaker, valued for his ability to communicate complex ideas with clarity and strategic insight. His lectures consistently bridge foundational theory, current research challenges, and future directions, making them highly relevant to both established researchers and early-career scientists.
Beyond individual achievements, Professor Rautenbach exerts lasting influence through extensive global collaborations and editorial leadership, including service as Editor-in-Chief and editorial board member of leading journals such as Discrete Mathematics, Theoretical Computer Science, and the Journal of Graph Theory. His combined research authority, international visibility, and academic stewardship position him as a key figure shaping the direction and standards of modern graph theory worldwide.
"Resilience of Rademacher chaos of low degree"
Elad Aigner-Horev, Ariel University, Israel
The resilience of a Rademacher chaos is the maximum number of adversarial sign flips it can tolerate without significantly changing its largest atom probability. Motivated by lower-bound results for linear Rademacher chaos (the Littlewood–Offord problem) by Bandeira, Ferber, and Kwan (Adv. Math., 2017), we establish probabilistic lower bounds on the resilience of Rademacher chaos of arbitrary (constant) degree.
Dr. Elad Aigner-Horev
Senior Lecturer & Chair, Department of Computer Science| Ariel University, Israel
Dr. Elad Aigner-Horev is a mathematician and computer scientist specializing in Extremal, Probabilistic, and Additive Combinatorics, with strong expertise in High-Dimensional Probability and its connections to Machine Learning and Data Science. He received his Ph.D. in Computer Science from Ben-Gurion University of the Negev in 2011.
Following his Ph.D., Dr. Aigner-Horev held postdoctoral positions at Hamburg University and at the University of Oxford, gaining broad international research experience at leading centers in combinatorics and probability. Since 2015, he has been a faculty member at Ariel University, where he currently serves as Chair of the Department of Computer Science (2023–2026).
Dr. Aigner-Horev has published extensively in leading journals, including SIAM Journal on Discrete Mathematics, Random Structures & Algorithms, European Journal of Combinatorics, Electronic Journal of Combinatorics, and Journal of Graph Theory. In addition to his research articles, he has authored numerous advanced lecture-note books and course monographs on extremal and random graph theory, spectral graph theory, optimization, probability, and data science. He is a frequent invited and plenary speaker at major international conferences, making him a distinguished and highly suitable Keynote Speaker for GAML 2026.
"Polynomial Local Search: The complexity of finding a local optimum"
Dominik Scheder | Technische Universität Chemnitz, Germany
How difficult is it to find a local optimum? Imagine a graph (G = (V,E)). We want to color the vertices blue and red, and our goal is to maximize the number of edges seeing both colors (“colorful” edges). This is Max-Cut, a problem well known to be NP-hard and also hard to approximate. But what if we only want to find a local coloring, i.e., one that cannot be improved by re-coloring only a single vertex?
“Just re-color vertices as long as it improves things” seems to work just fine. After all, the number of colorful edges cannot exceed (|E|), so we will be done soon. However, this reasoning breaks down if the edges have weights.
Asking how difficult it is to find such a local optimum leads to the complexity class PLS (Polynomial Local Search), defined by Johnson, Papadimitriou, and Yannakakis in 1988.
In this talk, based on joint work with Johannes Tantow, I will introduce the class PLS, present a typical reduction used to prove PLS-completeness, and sketch some recent developments.
Prof. Dr. Dominik Scheder
Professor of Theoretical Computer Science at Technische Universität Chemnitz, Germany
Prof. Dominik Scheder he has held the chair of Theoretical Computer Science since April 2024. He studied Computer Science at Friedrich-Alexander-Universität Erlangen-Nürnberg and completed a Master’s degree in Computer Science at University of Colorado Boulder. He received his Ph.D. from ETH Zürich with a dissertation on Algorithms and Extremal Properties of SAT and CSP. Following his doctoral studies, he conducted research visits at Aarhus University, Simons Institute for the Theory of Computing at University of California, Berkeley, and Tsinghua University. From 2014 to 2022 he served as Assistant and later Associate Professor at Shanghai Jiao Tong University. He subsequently held a temporary professorship at Hochschule Zittau/Görlitz from 2022 to 2024. His research focuses on algorithms and computational complexity, particularly algorithms for NP-complete problems, satisfiability (SAT), and the complexity of Boolean circuits.