AF: Small: New Tools to Analyze Random Walks

University Of Washington, Seattle WA

Investigators

Abstract

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.