Message passing algorithms, information-theoretic thresholds and computational barriers

计算机科学及其应用中的许多关键问题可以最好地描述为推理问题。 这里的目标是在间接的、可能有噪声的观察的基础上学习某些变量的值。 组测试问题就是一个很好的例子。 群体测试的目标是确定一个群体中感染某种疾病的个体。 为此，进行合并测试，其中每个人参加一个或多个测试池。 当且仅当测试池中至少有一个个体被感染时，测试池的结果应该是阳性的。 然而，测试结果可能并不完全准确。 在任何基地，都需要根据测试结果尽可能地识别受感染的个体。根据精确的设置，推理任务（如群体测试）可能是可行的，很难或不可能解决。 可行意味着存在一种有效的算法，可以根据观察到的数据可靠地解决问题。 困难意味着数据在原则上足以解决任务，但这将需要过高的计算资源。 最后，如果从信息论的观点来看，数据是不充分的，解决推理任务是不可能的。这个项目的目标是从计算理论的严格观点来研究推理问题，根据它们的可行性对它们进行分类，并开发新的推理方案和算法。在项目的第二阶段，我们将对非贝叶斯最优设置特别感兴趣。 这意味着推理算法可能无法精确地知道问题参数。 例如，在组测试问题中，推理算法可能仅具有对感染率和测试准确性的粗略估计。 我们要研究的第二个新挑战是自适应推理任务。 在这里，推理问题可以在几个阶段中交互式地处理，以改善结果。 例如，在分组测试中，这意味着测试不是同时进行的，而是分几个阶段进行的。 除了这些新的挑战，我们还将致力于完成对基本贝叶斯最优场景的严格理解。

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.