Personen

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.

Preprints

O. Gebhard, M. Hahn-Klimroth, O. Parczyk, M. Penschuck, M. Rolvien, J. Scarlett, N. Tan: Near optimal sparsity-constrained group testing: improved bounds and algorithms.

A. Coja-Oghlan, M. Hahn-Klimroth, P. Loick, B. F. Mezei, G. B. Sorkin: The Ising antiferromagnet and max cut on random regular graphs.

A. Coja-Oghlan, M. Hahn-Klimroth, P. Loick, N. Müller, K. Panagiotou, M. Pasch: Inference and mutual information on random factor graphs.

O.Gebhard, O.Johnson, P.Loick, M.Rolvien: Improved Bounds for noisy Group Testing with constant tests per item

O. Gehbard, M. Hahn-Klimroth, P. Loick, D. Kaaser: Quantitative Group Testing in the Sublinear Regime.

Publications

A. Coja-Oghlan, O. Gebhard, M. Hahn-Klimroth, P. Loick: Information-theoretic and algorithmic thresholds for group testing. IEEE Transactions on Information Theory (2020), doi: 10.1109/TIT.2020.3023377.

A. Coja-Oghlan, O. Gebhard, M. Hahn-Klimroth, P. Loick: Optimal Group Testing. Proceedings of Thirty Third Conference on Learning Theory, in PMLR 125:1374-1388 (2020).

A. Coja-Oghlan, O. Gebhard, M. Hahn-Klimroth, P. Loick: Information-theoretic and algorithmic thresholds for group testing. Proc. 46th ICALP 43:1-14 (2019), doi: 10.4230/LIPICS.ICALP.2019.43.

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 @math.uni-frankfurt.de, all phone numbers start with +49 69 798.
From left to right: Oliver Gebhard, Amin Coja-Oghlan, Max Hahn-Klimroth, Philipp Loick