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

Random Networks and Deterministic Diffusion Processes

随机网络和确定性扩散过程

基本信息

批准号：
1700365
负责人：
Wesley Pegden
金额：
$ 24万
依托单位：
Carnegie-Mellon University
依托单位国家：
美国
项目类别：
Continuing Grant
财政年份：
2017
资助国家：
美国
起止时间：
2017-06-01 至 2022-05-31
项目状态：
已结题

来源：
https://www.nsf.gov/awardsearch/showAward?AWD_ID=1700365&HistoricalAwards=false
关键词：
Random Networks Deterministic Diffusion Processes

项目摘要

This project aims to better understand random and pseudorandom processes and the interplay between them. For example, one major focus of the project is a model from statistical physics that replicates power-law behavior seen in the distributions of the frequencies of earthquakes, avalanches, etc. This model exhibits behavior of striking complexity resulting from simple rules, and is a natural de-randomization of related stochastic models from physics. Another aim of this project involves new kinds of probabilistic analyses of algorithms. These may, for example, give guidance on which algorithms may be efficient for "typical" inputs, and which will not. Finally, this project supports the education and mentorship of undergraduates through opportunities for engagement in research. This proposal concerns two principal research directions. The first concerns a pseudorandom diffusion process -- the Abelian sandpile -- which is at the same time both extremely simple in its mechanics, and extremely complex in its behavior. The rich fractals produced by the model had frustrated decades of inquiry. This project aims to extend the mathematical framework recently developed by the principal investigator and collaborators; for example, to understand the effect the choice of underlying lattice has on the behavior of the sandpile. The second area concerns new kinds of probabilistic analyses of point configurations and networks. For example, the question of the length of the shortest cycle through a collection of points in the plane is the Traveling Salesman Problem for Euclidean space, a problem of both classical theoretical interest and immediate practical utility (in transport problems, drilling problems, etc.). A major educational goal of the project is the mentorship of undergraduate research; the investigator has experience in designing courses and research seminars that have been effective for this goal.

该项目旨在更好地理解随机和伪随机过程以及它们之间的相互作用。例如，该项目的一个主要焦点是统计物理学模型，该模型复制了地震，雪崩等频率分布中的幂律行为。该模型表现出由简单规则产生的惊人复杂性，并且是物理学相关随机模型的自然去随机化。该项目的另一个目标涉及算法的新类型的概率分析。例如，这些可以指导哪些算法对于“典型”输入可能是有效的，哪些将不是。最后，该项目通过参与研究的机会支持本科生的教育和指导。这项建议涉及两个主要的研究方向。第一个问题涉及一个伪随机扩散过程-阿贝尔沙堆-这是在同一时间都非常简单的机制，并在其行为非常复杂。这个模型产生的丰富的分形使几十年的研究受挫。该项目旨在扩展主要研究者和合作者最近开发的数学框架;例如，了解底层晶格的选择对沙堆行为的影响。第二个领域涉及点结构和网络的新型概率分析。例如，通过平面上一组点的最短圈的长度问题是欧几里德空间的旅行商问题，这是一个既有经典理论意义又有直接实际效用的问题（在运输问题，钻井问题等）。该项目的一个主要教育目标是指导本科生的研究;调查员在设计课程和研究研讨会，已有效地实现这一目标的经验。

项目成果

期刊论文数量（13）

专著数量（0）

科研奖励数量（0）

会议论文数量（0）

专利数量（0）

A note on the localization number of random graphs: Diameter two case

关于随机图定位数的注记：直径二情况

DOI：
10.1016/j.dam.2018.06.006
发表时间：
2019
期刊：
Discrete Applied Mathematics
影响因子：
1.1
作者：
Dudek, Andrzej;Frieze, Alan;Pegden, Wesley
通讯作者：
Pegden, Wesley

Separating subadditive Euclidean functionals

分离次加法欧几里得泛函

DOI：
发表时间：
2017
期刊：
Random structures & algorithms
影响因子：
1
作者：
Frieze, A;Pegden, W
通讯作者：
Pegden, W

On the rank of a random binary matrix

关于随机二元矩阵的秩

DOI：
10.1137/1.9781611975482.58
发表时间：
2019
期刊：
Proceedings of the annual ACM-SIAM Symposium on Discrete Algorithms
影响因子：
0
作者：
Cooper, Colin;Frieze, Alan;Pegden, Wesley
通讯作者：
Pegden, Wesley

Assessing significance in a Markov chain without mixing

DOI：
10.1073/pnas.1617540114
发表时间：
2017-03-14
期刊：
PROCEEDINGS OF THE NATIONAL ACADEMY OF SCIENCES OF THE UNITED STATES OF AMERICA
影响因子：
11.1
作者：
Chikina, Maria;Frieze, Alan;Pegden, Wesley
通讯作者：
Pegden, Wesley

On random multi-dimensional assignment problems

关于随机多维分配问题