18.05.2026 14:30 Eleon Bach: Beyond Smoothed Analysis: Analyzing the Simplex Method by the Book
Narrowing the gap between theory and practice is a longstanding goal of the algorithm analysis community.
In this talk we discuss the new by the book algorithm analysis framework.
In contrast to earlier frameworks, by the book analysis not only models an algorithm's input data, but also the algorithm itself.
Results from by the book analysis are meant to correspond well with established knowledge of an algorithm's practical behavior, as they are meant to be grounded in observations from implementations, input modeling best practices, and measurements on practical benchmark instances.
Furthermore, we apply our framework to the simplex method, an algorithm which is beloved for its excellent performance in practice and notorious for its high running time under worst-case analysis.
The simplex method similarly showcased the state of the art framework smoothed analysis (Spielman and Teng, STOC'01).
We prove that under input scaling assumptions, feasibility tolerances and other design principles used by simplex method implementations, the simplex method indeed attains a polynomial running time.
This is joint work with Alexander Black, Sophie Huiberts and Sean Kafer and it is to appear at STOC'26.
Source
18.05.2026 15:00 Maximilian Engel: Stochastic inertia: How noise can extend dynamical regime lifetimes
We investigate the lifetime of dynamical regimes under the impact of noise. One may expect that the inclusion of noise tends to make the system leave prescribed regions of the state space faster. However, for relevant systems with complexities ranging from phenomenological toy models to reduced models of atmospheric dynamics, this intuition has proven misleading. As long as the noise is sufficiently small, the noisy system stays in regimes of interest on average longer than its deterministic counterpart, an effect we call "stochastic inertia".
We derive a formula to compute whether or not stochastic inertia occurs. Additionally, we propose a numerical technique for testing the occurrence of stochastic inertia, using a Markov chain on the set of points given by a sufficiently long trajectory of the system without noise. The method is shown to correctly predict the presence of stochastic inertia in simple systems, and its utility is demonstrated on a paradigm model of atmospheric dynamics.
This is joint work with R. Chemnitz, P. Koltai, S. Pfahl and H. Schoeller.
Source
18.05.2026 16:15 Maximilian Semenowicz: Normal Forms for Rough Differential Equations
We aim to provide the foundation for extending normal form theory from stochastic to rough differential equations. We address the existence of normal forms for rough ordinary differential equations, assuming suitable smoothness and the hyperbolicity of an equilibrium point. In this context, we establish local formal equivalence of the two solution flows generated by a random nonlinear RDE and its linearized version.
Source
18.05.2026 16:30 Alan Sergeev: Majority Dynamics on Graphs
Given a simple graph G = (V, E) and a map l0 : V → {+1, −1}, the majority dynamics
on G with initial assignment of states l0 is a process that begins on day 0, and for each
t ≥ 0 produces a new assignment of states lt+1 where each vertex takes the state of
the majority of its neighbours, and remains at its previous state in the case of a tie.
Specifically, for each v ∈ V ,
lt+1(v) =
(
+1 if P
u∈N (v) lt(u) > 0, or P
u∈N (v) lt(u) = 0 and lt(v) = +1,
−1 otherwise. (1)
This process is a model for opinion exchange dynamics, with applications in many areas,
such as politics, sociology, biophysics. While there exist results about the process even-
tually reaching a 2-periodic stable state on all graphs, a natural question to study would
be under which initial conditions is unanimity reached, and how quickly.
When considering the question specifically in the case of Binomial Random Graphs, a
longstanding conjecture, due to Benjamini, Chan, O’Donnel, Tamuz and Tan (2016) is
the following:
Conjecture. Let G ∼ G(n, p) be the binomial random graph with p = ω(1/n) and l0(v)
be sampled uniformly at random from {+1, −1} for each v ∈ V . Then w.h.p. the majority
dynamics process reaches unanimity after sufficiently many steps t.
Steps towards proving the conjecture have been taken taken by gradually improving the
range densities d = np for which the conjecture is known to be true, with the current
best bound being d ≫ n1/3 log2/3 n due to Kim and Tran. Our work aims to prove the
conjecture for the range n1/4 ≪ d ≤ O(n1/3), and lays the groundwork for proving the
conjecture in the general case n1/(k+1) ≪ d ≤ O(n1/k).
This is based on joint work with Nikolaos Fountoulakis, University of Birmingham.
Source
20.05.2026 12:15 Veronica Vinciotti (University of Trento, IT): Causal discovery in dynamic networks
In network science, as in other applied fields, answering key questions often requires distinguishing causal mechanisms from context-dependent associations. One formalization of causality uses invariance: a relationship between a target variable and a set of covariates is causal if it remains stable across diverse environments or interventions. Originally developed for linear models, this approach has been extended to more flexible frameworks, including generalized linear models, where causality is expressed via Pearson risk invariance.
In this talk, we extend causal invariance to dynamic networks, focusing on Relational Event Models (REMs), which describe instantaneous interactions over time between social actors. Because the target —the dynamic network— and potential causal drivers are stochastic processes, dependences among them are characterized using conditional local independence. By exploiting a connection between REMs and logistic regression, we extend Pearson risk invariance to this dynamic setting, producing a causal discovery algorithm that only requires data from a single observational environment. We show how this approach is able to identify, and distinguish, important causal mechanisms in network science, such as social influence and homophily.
This is joint work with Melania Lembo and Ernst Wit (USI).
Source