Friday Seminar Summer 2025

Zoom Link

May 23

When: 15:00 (CET) on Friday
Where: G-210 and via Zoom

Speaker: Henry Austin

Title: Understanding stateless broadcast on synchronous networks

Abstract:

Broadcast is a fundamental problem in distributed computing, with many algorithms requiring storing either control information or predetermined structures (e.g. a spanning tree). Amnesiac Flooding as introduced by Hussak and Trehan (2019), allows for terminating broadcast on synchronous networks without either. In fact, it neither requires agents to retain information between rounds nor make routing decisions based on message contents. We present a number of recent results regarding the algorithm. First, we show that it is the only deterministic algorithm with the aforementioned properties. Secondly, we present a termination dichotomy over its configuration space, capturing the structural components that drive termination and non-termination. Finally, we apply these results to investigate the fault sensitivity of the algorithm and find it to be extremely fault sensitive.

June 20

When: 14:00 (CET) on Friday
Where: G-210 and via Zoom

Speaker: Arnab Chatterjee

Title: Belief Propagation Guided Decimation on Random k-XORSAT 

Abstract:

We analyse the performance of Belief Propagation Guided Decimation, a physics-inspired message passing algorithm, on the random k-XORSAT problem. Specifically, we derive an explicit threshold up to which the algorithm succeeds with a strictly positive probability Ω(1) that we compute explicitly, but beyond which the algorithm with high probability fails to find a satisfying assignment. In addition, we analyse a thought experiment called the decimation process for which we identify a (non-) reconstruction and a condensation phase transition. The main results of the present work confirm physics predictions from [RTS: J. Stat. Mech. 2009] that link the phase transitions of the decimation process with the performance of the algorithm, and improve over partial results from a recent article [Yung: Proc. ICALP 2024].