AF: Small: New Tools to Analyze Random Walks

随机漫步和马尔可夫链是最实用的算法原语之一，在科学领域有着广泛的应用。它们主要用于许多现代技术行业，如搜索引擎或社交网络。同时，它们作为模拟和检验几乎所有科学领域中几乎任何科学理论的首选方法。尽管在过去的几十年里进行了大量的研究，但关于随机漫步的行为仍然有许多未解决的问题。这个提议的主要目标是更好地理解这些随机过程；特别是，目的是了解随机行走者的分布几乎与起始位置无关需要多长时间。在过去的五年中，基于与高维膨胀理论建立的密切联系，马尔可夫链的分析已经发生了革命性的变化。因此，几十年来许多悬而未决的问题得到了解决。在这个项目中，研究者的目标是在随机漫步出现的其他（理论）计算机科学领域中利用这种新机器。特别是，研究者计划将其用于设计基础优化问题的近似算法，研究高维组合学中生成树的推广等。该项目的目标是为我们对随机漫步的理解提供新的线索，这可以使广泛的科学界受益。该奖项反映了美国国家科学基金会的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

Random walks and Markov chains are one of the most practical algorithmic primitives with applications all over the science. They are primarily used in many modern technological industries, such as search engines or social networks. At the same time, they serve as the first method of choice in simulating and testing almost any scientific theory in nearly all areas of science. Despite significant research over the last few decades, there are still many unresolved questions on the behavior of random walks. The primary goal of this proposal is to better understand these stochastic processes; in particular, the aim is to understand how long it takes for the distribution of the random walker to be almost independent of the starting position.Over the last five years, the analysis of Markov chains has been revolutionized based on the close connections built with the theory of high dimensional expanders. As a consequence, many problems that have been left open for decades got resolved. In this project, the investigator aims to exploit this new machinery in other (theoretical) computer science areas where random walks appear. In particular, the investigator plans to use them in designing approximation algorithms for foundational optimization problems, study generalizations of spanning trees in high dimensional combinatorics, etc. The goal of the project is to shed new light on our understanding of random walks, which can benefit a wide range of scientific communities.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.