AF: Small: Approximating Characteristic Polynomial of Matroids

随机算法代表了一种优雅的，有时是唯一已知的方法，用于解决一些难以解决的现实问题。在一组对象上的概率分布的概念对于许多随机化算法是必不可少的。例如，Google？的PageRank方法来对搜索结果进行排名，实际上定义了一组网页的概率分布。一大类随机化算法依赖于从可能输入上的某些期望概率分布生成样本。马尔可夫链是一种最有趣、最突出和最有用的结构，因为它们能够从期望的概率分布中生成和抽取样本。这个项目是关于开发和改进马尔可夫链为基础的算法的几个基本问题，使用一种新的数学技术称为？多项式的几何学？该项目的成果将应用于许多科学和技术领域，如机器学习，统计物理和量子力学。PI打算实现他将在本项目中研究的算法，并将其提供给研究人员。该建议包括通过新的研究生课程将研究和教学结合起来，向数学和工程系的学生介绍这一领域的新技术。虽然该项目以理论计算机科学为基础，但也将吸引许多对马尔可夫链分析感兴趣的概率论、组合学、统计学和统计物理学的研究生。此外，PI计划培养具有不同性别和种族的优秀本科生和研究生。在过去的几十年里，研究人员已经开发了几种技术来约束马尔可夫链的混合时间。在大多数情况下，这些技术是“本地的”，并且当底层组合结构复杂时，它们不能限制混合时间。因此，需要新的“全球”技术系列，这些技术可以克服多年来未能屈服于传统方法的障碍。 这个项目的主要目的是研究一个新的“全球”机制的基础上高维扩展和多项式的几何领域的隐藏权力。高维扩展器起源于数学，是扩展器图的自然推广。它们在复杂性理论和编码理论中被证明是有用的。最近，PI及其合作者利用高维展开子作为分析拟阵采样基的马尔可夫链的新工具。在这个项目中，研究人员和他的团队计划进一步研究这个新工具，看看它是否可以用于近似计数领域的其他前沿。这个奖项反映了NSF的法定使命，并被认为是值得通过使用基金会的智力价值和更广泛的影响审查标准进行评估的支持。

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.