Discrete Random and Pseudorandom Structures

Carnegie Mellon University, Pittsburgh PA

Investigators

Abstract

This project aims to better understand random and pseudorandom processes, and the interplay between them. In particular, the project studies models from statistical physics of aggregation processes built on both random and pseudorandom walks. For example, in the former case, diffusion limited aggregation processes produce intricate fractals through processes analogous to those that drive the formation of corals, but the propensity of these processes to give rise to long, spiny, structures is still not rigorously understood. In the latter case, the Abelian sandpile process builds a cluster of particles through a pseudorandom distribution of particles that ends up giving rise to intricate fractal patterns, as well as statistical laws which reappear throughout nature (e.g., as the frequency distributions of earthquakes, avalanches, etc). Among other goals, this project aims to better understand the dependence of the behavior of the Abelian sandpile on the underlying lattice. One particularly interesting case is that where a periodic lattice is subjected to random edge-deletions; in this case the Abelian sandpile is a pseudorandom aggregation process on a random environment, which we expect to behave like a random aggregation process on a periodic environment. Other topics include work on Euclidean functionals; in particular, refining our understanding of asymptotic relationships between structures like Traveling Salesperson Tours through typical (i.e. random) point sets, and their algorithmic approximations. 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.