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
19.05.2026 16:15 Ian Jauslin: The liquid-vapor phase transition in a system with a finite but coarse-grained attraction
The standard approach to studying the liquid-vapor phase transition uses the
Maxwell double-tangent construction. Whereas this construction is easily
justified physically, deriving it mathematically has proved to be more
difficult. In 1966, Lebowitz and Penrose proved the Maxwell construction in a
mean field model, where the particles interact via a hard-core repulsion, and
an infinite range, infinitely weak attraction. Generalizing their result to
finite pair attractions remains an open problem.
In this talk, I will discuss a proof of the existence of a liquid-vapor phase
transition in a system with an attraction that is finite, but is also
coarse-grained. More precisely, we split up space into mesoscopic boxes, and
define an attraction that ignores the location of the particles within each
box. Defined in this way, our model is reflection positive, which allows us
to prove the existence of a liquid-vapor phase transition.
This is joint work with Qidong He, Joel L. Lebowitz, and Ron Peled.
Source