Log-concave polynomials II: high-dimensional walks and an FPRAS for counting bases of a matroid
From MaRDI portal
Publication:5212742
DOI10.1145/3313276.3316385zbMath1433.68606arXiv1811.01816OpenAlexW2963722886MaRDI QIDQ5212742
Kuikui Liu, Cynthia Vinzant, Nima Anari, Shayan Oveis Gharan
Publication date: 30 January 2020
Published in: Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1811.01816
Combinatorial aspects of matroids and geometric lattices (05B35) Asymptotic enumeration (05A16) Approximation algorithms (68W25) Randomized algorithms (68W20) Random walks on graphs (05C81)
Related Items (37)
Some Inapproximability Results of MAP Inference and Exponentiated Determinantal Point Processes ⋮ Logarithmic concavity of Schur and related polynomials ⋮ Logarithmic concavity for morphisms of matroids ⋮ Perfect Sampling in Infinite Spin Systems Via Strong Spatial Mixing ⋮ Lagrangian geometry of matroids ⋮ Counting vertices of integral polytopes defined by facets ⋮ Coboundary expansion, equivariant overlap, and crossing numbers of simplicial complexes ⋮ Swendsen-Wang dynamics for the ferromagnetic Ising model with external fields ⋮ Log-concave poset inequalities (extended abstract) ⋮ Modified log-Sobolev inequalities for strong-Rayleigh measures ⋮ On the convexity of general inverse \(\sigma_k\) equations ⋮ Expansion of random 0/1 polytopes ⋮ Essence of independence: Hodge theory of matroids since June Huh ⋮ Parameterized Counting and Cayley Graph Expanders ⋮ Approximation Algorithms for the Random Field Ising Model ⋮ Log-concave polynomials. II: High-dimensional walks and an FPRAS for counting bases of a matroid ⋮ Nowhere to go but high: a perspective on high-dimensional expanders ⋮ Interactions of computational complexity theory and mathematics ⋮ Combinatorics and Hodge theory ⋮ Complexity theory. Abstracts from the workshop held November 14--20, 2021 (hybrid meeting) ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Lorentzian polynomials ⋮ Modified log-Sobolev inequalities for strongly log-concave distributions ⋮ Acyclic polynomials of graphs ⋮ High order random walks: beyond spectral gap ⋮ Strictness of the log-concavity of generating polynomials of matroids ⋮ Log-concave polynomials. I: Entropy and a deterministic approximation algorithm for counting bases of matroids ⋮ Pfaffian pairs and parities: counting on linear matroid intersection and parity problems ⋮ Scalar Poincaré implies matrix Poincaré ⋮ Modified log-Sobolev inequalities, Beckner inequalities and moment estimates ⋮ Log concavity and concentration of Lipschitz functions on the Boolean hypercube ⋮ Approximately counting bases of bicircular matroids ⋮ Spectral Independence in High-Dimensional Expanders and Applications to the Hardcore Model ⋮ Introduction to the combinatorial atlas ⋮ Spaces of Lorentzian and real stable polynomials are Euclidean balls ⋮ Pfaffian Pairs and Parities: Counting on Linear Matroid Intersection and Parity Problems
This page was built for publication: Log-concave polynomials II: high-dimensional walks and an FPRAS for counting bases of a matroid
