Message passing algorithms, information-theoretic thresholds and computational barriers.

Project description

Certain fundamental computational challenges can best be described as inference problems. Many such inference tasks exhibit a gap between the fundamental information-theoretic lower bounds and the bounds reached by the best known efficient algorithms. Heuristic arguments suggest that these gaps may be the result of genuine computational intractability. The goal of this research project is to advance the rigorous mathematical understanding of inferece problems, both algorithmically and information-thereotically. Specific topics include the use and limitations of message-passing algorithms and applications to concrete problems such as group testing, decoding or other signal processing tasks.



  • Quantitative Group Testing in the Sublinear Regime
    O. Gebhard, D. Kaaser, M. Hahn-Klimroth, P. Loick
  • Optimal non-adaptive group testing
    A. Coja-Oghlan, O. Gebhard, M. Hahn-Klimroth, P. Loick
  • Optimal adaptive group testing
    M. Hahn-Klimroth, P. Loick



Project members

Name E-Mail Raum Durchwahl
Prof. Dr. Amin Coja-Oghlan (PI) acoghlan 308 25568
Oliver Gebhard gebhard 310 25572
Philipp Loick loick 310a 25573

All mail adresses end with, all phone numbers start with +49 69 798.

From left to right: Oliver Gebhard, Amin Coja-Oghlan, Max Hahn-Klimroth, Philipp Loick