Mathematical Institute Calendar

Thursday, January 27, 2022

16:00-17:00

Cancelled/postponed

Applied Mathematics Seminar -- Noela Müller (TU/e) — Belief Propagation on the random k-SAT model

see description

Corroborating a prediction from statistical physics, we prove that the Belief Propagation message passing algorithm approximates the partition function of the random k-SAT model well for all clause/variable densities and all inverse temperatures for which a modest absence of long-range correlations condition is satisfied. This condition is known as "replica symmetry" in physics language. From this result we deduce that a replica symmetry breaking phase transition occurs in the random k-SAT model at low temperature for clause/variable densities below but close to the satisfiability threshold. This is joint work with Amin Coja-Oghlan and Jean Bernoulli Ravelomanana.

Thursday, February 3, 2022

Thursday, February 10, 2022

Wednesday, March 2, 2022

Thursday, April 14, 2022

Thursday, June 16, 2022