Random Structures and Algorithms

该奖项支持对数学结构中随机性概念的基础研究。虽然随机性在计算机科学中的应用无处不在，但许多重要的计算和算法问题仍有待使用这一基本概念进行研究。尽管许多理论和实用的现代算法都很复杂，但随机性往往能够补救最坏情况，重点是平均情况和利用局部信息的随机算法。这包括被深入研究的问题，如所谓的旅行推销员问题，通过集中研究几何版本，其中有效的算法是可行的。该项目的一个重要方面是学生参与研究，这有望在项目的理论基础之外对数学和计算机科学产生广泛的影响。这个项目的一个特别重点是识别涉及图和有向图上随机游走的问题。基于最近的重大进展，将对所谓的哈希方案进行彻底的调查，检查仅使用局部信息的图上的搜索算法。经典的随机漫步就是这种算法的典型例子。目前对连接到全球网络随机模型的优先连接图的可用分析将扩展到更一般的图模型。一个统计检验已经被设计出来，用于检测一个声称来自马尔可夫链稳态的样本中的偏差。另一个研究方向是在线购买问题。在这类问题中，图的边被赋予随机的代价，并被顺序地呈现，它们必须被选择或拒绝。被接受的边缘被用来构建一个结构，目标是尽可能经济地构建这个结构。

This award supports foundational research into the concept of randomness in mathematical structures. While the use of randomness in computer science is ubiquitous, many important computational and algorithmic problems remain to be studied using this foundational concept. Despite the complexity of many theoretic as well as practical modern algorithms, randomness is frequently able to remedy the worst-case examples focusing on the average case examples and randomized algorithms which make use of local information. This includes such intensively studied problems as the so-called Travelling Salesperson problem, by concentrating on geometric versions where efficient algorithms are feasible. An important aspect of the project is the involvement of students in the research, which is expected to have a broad impact on mathematics and on computer science beyond the theoretical foundations of the project.A special focus of this project is to identify problems that involve random walks on graphs and digraphs. Based on significant recent progress, a thorough investigation of so-called hashing schemes will be undertaken, examining search algorithms on graphs that employ only local information. The classical random walk is a prime example of such an algorithm. The current available analysis for preferential attachment graphs, which are connected to random models of the world-wide web, will be extended to more general models of graphs. A statistical test has been devised for detecting bias in a sample claiming to be from the steady state of a Markov chain. Another line of research is on-line purchasing problems. In such problems, the edges of a graph are given random costs and are presented sequentially and they must be selected or rejected. The accepted edges are used to build a structure, and the goal is to build this structure as economically as possible.