AF: Small: Approximating Characteristic Polynomial of Matroids

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

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.