Grant: Discovery Grants Program - Individual

Markov Random Fields (MRFs) are a class of probabilistic graphical models that have widespread applications in many branches of science like Artificial Intelligence, Social Sciences, Physics, Chemistry, and Biology. These are multivariate distributions that satisfy properties akin to a probabilistic version of Occam's razor, which could be used to explain their ubiquity and success. A basic algorithmic problem is as follows: Given an implicitly defined MRF, sample either exactly or approximately from this distribution. This captures a wide variety of problems involving counting, or sampling discrete objects, such as stable matchings, independent sets in graphs, etc. More recently, these distributions have also found connections to random constraint satisfaction problems, and the Unique Games Conjecture, two of the central fields of study in theoretical computer science. Algorithms that sample from these distributions have traditionally been based on Markov chains, and have led to the uncovering of several deep and interesting phenomena for these distributions. More recently, we have seen the development of polymer methods for this same task. These methods can be used to sample from certain MRFs where no Markov chain-based algorithms are known, and seem to provide a much stronger probabilistic understanding of these distributions than before. In the plan that the present proposal focuses on, my students and I wish to extend polymer methods beyond their current capabilities on three different fronts. 1. Better applications of polymer methods: specifically, we wish to obtain faster algorithms for approximate counting problems which are known to be computationally hard, or whose complexity is currently unknown. 2. Understanding polymer methods for higher-order interactions: Most current methods for analyzing polymer models insist that the underlying MRF is defined by pairwise interactions. Given the immense use and widespread application that these methods have already found, a natural step is to overcome this limitation. This would open the door to many more applications. 3. Understanding polymer methods beyond current parameters: Typically, MRFs are defined by a set of parameters, that tightly control their behaviour. This behaviour is also intimately linked to whether or not efficient sampling is possible from these distributions. This line of research aims to push the parameters that polymer methods can handle, in order to help gain a better understanding of these distributions. Given the various applications of polymer methods in the last few years, all of the above are fruitful and impactful avenues of research that not will only enhance existing algorithmic techniques, but will also further build MRFs as a tool in the probabilistic analysis of several problems.