# Log-Concave Polynomials II: High-Dimensional Walks and an FPRAS for Counting Bases of a Matroid

arXiv: https://arxiv.org/abs/1811.01816 · HTML: https://mlsanity.com/paper/1811.01816/

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 5 Nov 2018.

## Built on by (most cited first, 7 of 7)

- [Batch Active Learning of Reward Functions from Human Preferences](https://mlsanity.com/paper/2402.15757/) (2024)
- [From Sampling to Optimization on Discrete Domains with Applications to Determinant Maximization](https://mlsanity.com/paper/2102.05347/) (2021)
- [Some Inapproximability Results of MAP Inference and Exponentiated Determinantal Point Processes](https://mlsanity.com/paper/2109.00727/) (2021)
- [Arithmetic Circuits and Neural Networks for Regular Matroids](https://mlsanity.com/paper/2511.02406/) (2025)
- [Learning Arithmetic Formulas in the Presence of Noise: A General Framework and Applications to Unsupervised Learning](https://mlsanity.com/paper/2311.07284/) (2023)
- [Computational Complexity of Normalizing Constants for the Product of Determinantal Point Processes](https://mlsanity.com/paper/2111.14148/) (2021)
- [Almost linear time differentially private release of synthetic graphs](https://mlsanity.com/paper/2406.02156/) (2024)

## Abstract (arXiv)

We design an FPRAS to count the number of bases of any matroid given by an independent set oracle, and to estimate the partition function of the random cluster model of any matroid in the regime where 0<q<1. Consequently, we can sample random spanning forests in a graph and (approximately) compute the reliability polynomial of any matroid. We also prove the thirty year old conjecture of Mihail and Vazirani that the bases exchange graph of any matroid has expansion at least 1. One of our key observations is a close connection between pure simplicial complexes and multiaffine homogeneous polynomials. Specifically, if X is a pure simplicial complex with positive weights on its maximal faces, we can associate with X a multiaffine homogeneous polynomial pX such that the eigenvalues of the localized random walks on X correspond to the eigenvalues of the Hessian of derivatives of pX.