AF: Small: Approximating Characteristic Polynomial of Matroids

University Of Washington, Seattle WA

Investigators

Abstract

Randomized algorithms represent an elegant and sometimes only known approach for solving some intractably hard real-life problems. The notion of probability distribution over a set of objects is essential to many randomized algorithms. For example, Google?s PageRank approach to ranking search results in effect defines a probability distribution over the set of webpages. A large class of randomized algorithms rely on generating samples from some desired probability distribution over possible inputs. Markov Chains have been one the most interesting, prominent and useful structures because of their ability to generate and draw samples from desired probability distributions. This project is about developing and improving Markov-Chain-based algorithms for several fundamental problems using a new mathematical technique called ?Geometry of Polynomials?. The results from this project will have applications in a number of areas of science and technology such as machine learning, statistical physics, and quantum mechanics. The PI intends to implement algorithms that he will study in this project and make them available to researchers. This proposal includes integration of research and teaching by means of new graduate courses to introduce new techniques in this field to students in mathematics and engineering departments. Although grounded in theoretical computer science, the project will also attract many graduate students in probability theory, combinatorics, statistics, and statistical physics who are interested in the analysis of Markov chains. Furthermore, the PI plans to train strong undergraduate and graduate students with diverse gender and ethnicity. Over the last few decades researchers have developed several techniques to bound the mixing time of Markov chains. In most cases, these techniques are "local?, and they fail to bound the mixing time when the underlying combinatorial structure is complex. So, there is a need for new families of ``global'' techniques that can overcome barriers that have failed over the years to yield to classical methods. The main purpose of this project is to investigate the hidden power of a new "global" machinery based on high-dimensional expanders and the field of geometry of polynomials. High-dimensional expanders originated in mathematics and are a natural generalization of expander graphs. They have proved to be useful in complexity theory, and coding theory. Recently, high dimensional expanders were exploited by the PI and collaborators as a new tool in the analysis of Markov chains for sampling bases of matroids. In this project the researcher and his team plan to further investigate this new tool and see if it can be used at other frontiers of the field of approximate counting. 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.