Random Networks and 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.