Thresholds and algorithms in Bayesian inference

Abstract

The thesis “Thresholds and Algorithms in Bayesian Inference” is studying phase transitions in different settings. Given a probabilistic structure that is defined by local interactions that vary depending on one or multiple parameters, the behaviour of this system can change dramatically, macroscopically, due to changes of the local interactions. These drastic changes are called phase transitions. Prime example for these transitions appear in so called Bayesian inference problems, where the outcome of a probabilistic process is observed with the aim to infer further information of the system. To infer this information can be either easy, computationally hard, or information theoretically impossible (i.e., every algorithm fails with probability tending to 1), depending on the specific model as well as the parameters. In this thesis, these thresholds are studied in three different models: two different settings of Group Testing, the random k-XORSAT model and the Patient Zero problem. This work contributes thresholds for all of these models and, in the case of group testing and the Patient Zero problem, efficient algorithms that achieve optimal results.