Combinatorics, Probability and Algorithms

点击翻译按钮获取中文摘要

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.