Combinatorics, Probability and Algorithms

组合学，概率论及其应用（特别是算法）的接口已经发展成为一个令人兴奋的领域，具有联系和应用，例如理论计算机科学，统计物理和运筹学。该项目将侧重于这一领域具有相互关联目标的三个主题：(i)随机算法，特别侧重于随机属性测试：属性测试旨在从局部随机抽样算法推断全局结构。更准确地说，给定一个组合对象，我们的目标是非常快地区分它是否满足某些性质，或者它是否远远不满足这个性质。因此，主要目标是设计随机算法，只考虑输入的一小部分，然后以高概率区分上述两种情况。（ii）随机离散结构：研究随机图的动机是理解对象的典型行为。这一领域与统计物理学（特别是对相变的研究，其中微小的参数变化会引起重大的结构变化）有联系，并支持算法的平均案例分析以及网络过程（例如流行病性质）的研究。我们将集中讨论由局部约束和复杂网络定义的概率模型的全局结构。（iii）随机构造：本主题涉及使用随机过程来构建具有所需属性的组合对象，重点关注长期存在的图分解问题。（这类问题的主要目的是将一个大物体分割成合适的小块，这在统计测试和信息论中都有应用。）该项目的目的是在这三个主题的核心问题上取得决定性进展，其解决方案依赖于组合学和概率论之间的相互作用。这三个主题有几个共同的特点。例如，许多目标背后的一个基本范例是“局部-全球”结构：局部模式如何影响（典型的）全球结构？在过去的几十年里，对这种范式的研究在极值组合学领域取得了巨大的成果。在项目中，我们将从概率的角度考虑这一点。这与计算问题特别相关，其中考虑的图很大：在“传统”图理论问题中，整个图是精确给定的，但对于大型网络，这通常不再是这种情况。因此，我们需要从局部考虑中推断出它们的全局属性。

The interface of Combinatorics, Probability and its applications (in particular to algorithms) has been developing into an exciting area, with connections and applications, e.g. to Theoretical Computer Science, Statistical Physics and Operations Research. The project will focus on three themes in this area with interrelated objectives:(i) Randomized Algorithms with a particular focus on randomized property testing:Property testing aims to infer global structure from local random sampling algorithms. More precisely, given a combinatorial object, we aim to distinguish very quickly if it satisfies some property or if it is far away from satisfying this property. So the main goal is to design randomized algorithms which only consider a tiny part of the input, and then distinguish with high probability between the two above cases.(ii) Random Discrete Structures:The study of random graphs is motivated by understanding the typical behaviour of objects. This area has connections to statistical physics (in particular, the study of phase transitions, where small parameter changes give rise to major structural changes) and underpins the average case analysis of algorithms as well as the study of network processes, e.g. of epidemic nature. We will concentrate on the global structure of probability models defined by local constraints as well as on complex networks.(iii) Randomized Constructions:This theme is concerned with the use of randomized processes to build combinatorial objects with desired properties, with a focus on longstanding graph decomposition problems. (The main aim in such problems is to split a large object into suitable small pieces, which has applications, e.g. in statistical testing and information theory.)The aim of the project is to make decisive progress on central questions within these three themes, whose solution relies on the interplay between Combinatorics and Probability. The three themes are connected by several common features. For example, a fundamental paradigm underlying many of the objectives is that of "local-global" structure: how do local patterns influence (typical) global structure? The investigation of this paradigm has been enormously fruitful in the field of Extremal Combinatorics over the last few decades. Within the project we will consider this from a probabilistic perspective. This is particularly relevant for computational problems where the graphs under consideration are large: in "traditional" graph theoretical problems the whole graph is exactly given, but for large networks this is often no longer the case. So we need to infer their global properties from local considerations.