Message passing algorithms, information-theoretic thresholds and computational barriers

• Applicant: Professor Dr. Amin Coja-Oghlan
• Subject Area: Theoretical Computer Science
• Term: since 2018
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 393689644

Numerous critical problems in computer science and its applications can best be characterised as inference problems. Here the objective is to learn the values of certain variables on the basis of indirect, possibly noisy observations. The group testing problem is an excellent example. The goal in group testing is to identify those individuals within a group that are infected with a disease. To this end pooled tests are conducted where each individual takes part in one or more test pools. The result of a test pool should be positive if and only if at least one of the individuals in that pool are infected. However, the test results may not be entirely accurate. In any base, on the basis of the test results the infected individuals need to be identified as best as possible.Depending on the precise setup, inference tasks such as group testing may be feasible, hard or impossible to solve. Feasible means that there exists an efficient algorithm that can reliably solve the problem on the basis of the observed data. Hard means that the data suffices to solve the task in principle, but this would require exorbitant computational resources. Finally, if the data are insufficient from an information-theoretic viewpoint, solving the inference task is impossible.The goal of this project is to investigate inference problems from the rigorous viewpoint of the theory of computing, to classify them according to their feasiblity, and to develop new inference schemes and algorithms.In the second phase of the project we will be particularly interested in the non-Bayes optimal setting. This means that the inference algorithm may not know the problem parameters precisely. For example, in the group testing problem the inference algorithm may only have a rough estimate of the infection rate and of the accuracy of the tests. A second new challenge that we are going to investigate is adaptive inference tasks. Here the inference problem can be tackled interactively in several stages to improve results. For example, in group testing this means that tests are not conducted concurrently but in several stages. Beyond these new challenges we will also aim to complete the rigorous understanding of the fundamental Bayes-optimal scenario.

• DFG Programme: Research Grants