AF: Markov Chain Algorithms for Problems from Computer Science, Statistical Physics and Economics

点击翻译按钮获取中文摘要

The PI's research explores fundamental relationships between physical systems and the efficiency of algorithms, looking at applications in Economics, Nanotechnology, Computing and Physics that can benefit from this joint lens. For instance, the Schelling model of segregation was developed in the economics community in 1971. In this model, residents within a community assess their personal comfort with the racial distribution in their local neighborhood and they are more inclined to move if they are dissatisfied. Schelling showed that even if every member of the community is satisfied with having half of their neighbors be of the opposite race, even small preference for one's own race leads to global segregation. Thus, micromotives can bring about macrobehavior without any centralized influence. The PI will explore variants of this model for 2-dimensional models using insights from computing and physics.The PI will also consider natural stochastic processes occurring in the context of self-organizing lists and nanotechnology. The first is a fundamental question about biased permutations arising from list update algorithms for minimizing total search costs. The problem can be modeled as a question about permutations under nearest-neighbor transpositions in which items are biased to be put in the correct order. The second is a nanotechnology problem concerning growth processes arising in the context of tile-based self-assembly, where tiles are constructed from DNA. The rates of convergence of these two sampling algorithms are closely related, and the PI has developed new approaches to try to better understand their convergence properties.Last, the award addresses fundamental questions at the interface of computing and physics. Determining the mixing time of Markov chains is often the vital step in proving the efficiency of many approximation algorithms based on random sampling. One of the richest sources for sampling problems is statistical physics, where the state space of the Markov chain represents the states of a physical system and sampling lends insight into the thermodynamic properties of the model. By exploring parallels between phase transitions in both fields, the PI will address fundamental questions about physical systems while searching for better approaches to sampling.