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.