权益分类	功能权益	普通用户	{{item.name}}会员
{{category.name}}	{{benefitItem.name}}

Combinatorics, Probability and Algorithms

组合学、概率和算法

基本信息

批准号：
EP/N019504/1
负责人：
Daniela Kuehn
金额：
$ 104.79万
依托单位：
University of Birmingham
依托单位国家：
英国
项目类别：
Fellowship
财政年份：
2016
资助国家：
英国
起止时间：
2016 至无数据
项目状态：
已结题

来源：
https://gtr.ukri.org/projects?ref=EP%2FN019504%2F1
关键词：
Combinatorics Probability 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.

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