Log-concave polynomials. II: High-dimensional walks and an FPRAS for counting bases of a matroid
From MaRDI portal
Publication:6181233
DOI10.4007/annals.2024.199.1.4OpenAlexW2898617375MaRDI QIDQ6181233
Cynthia Vinzant, Shayan Oveis Gharan, Kuikui Liu, Nima Anari
Publication date: 2 January 2024
Published in: Annals of Mathematics. Second Series (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.4007/annals.2024.199.1.4
Approximation algorithms (68W25) Graph theory (05Cxx) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87) Enumerative combinatorics (05Axx) Designs and configurations (05Bxx)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- \(\lambda_ 1\), isoperimetric inequalities for graphs, and superconcentrators
- Geometric bounds for eigenvalues of Markov chains
- The Lee--Yang and Pólya--Schur programs. I: Linear operators preserving stability
- Two remarks concerning balanced matroids
- Inapproximability of the Tutte polynomial
- Random weighting, asymptotic counting, and inverse isoperimetry
- A polynomial-time algorithm to approximate the mixed volume within a simply exponential factor
- Random generation of combinatorial structures from a uniform distribution
- Eigenvalues and expanders
- The broken-circuit complex: its structure and factorizations
- The computational complexity of knot and matroid polynomials
- On \(L^2\)-cohomology and property (T) for automorphism groups of polyhedral cell complexes
- Homogeneous multivariate polynomials with the half-plane property
- Random cluster dynamics for the Ising model is rapidly mixing
- Hodge theory for combinatorial geometries
- Enumeration of points, lines, planes, etc.
- Local spectral expansion approach to high dimensional expanders. I: Descent of spectral gaps
- Elementary bounds on Poincaré and log-Sobolev constants for decomposable Markov chains
- Inapproximability of the Tutte polynomial of a planar graph
- Approximating the Tutte polynomial of a binary matroid and other related combinatorial polynomials
- High order random walks: beyond spectral gap
- Log-concave polynomials. I: Entropy and a deterministic approximation algorithm for counting bases of matroids
- Lorentzian polynomials
- Modified log-Sobolev inequalities for strongly log-concave distributions
- Pólya-Schur master theorems for circular domains and their boundaries
- Polynomials with the half-plane property and matroid theory
- p-adic curvature and the cohomology of discrete subgroups of p-adic groups
- Determinantal Point Processes for Machine Learning
- Discrete Concavity and the Half-Plane Property
- Multivariate stable polynomials: theory and applications
- Negative dependence and the geometry of polynomials
- Polynomial-Time Approximation Algorithms for the Ising Model
- Approximating the Partition Function of the Ferromagnetic Potts Model
- The Lee‐Yang and Pólya‐Schur programs. II. Theory of stable polynomials and applications
- On multivariate Newton-like inequalities
- The Broken-Circuit Complex
- High Dimensional Random Walks and Colorful Expansion
- On the computational complexity of the Jones and Tutte polynomials
- Approximately counting bases of bicircular matroids
- The Complexity of Computing the Sign of the Tutte Polynomial
- HIGH DIMENSIONAL EXPANDERS
- Log-concave polynomials II: high-dimensional walks and an FPRAS for counting bases of a matroid
- A Polynomial-Time Approximation Algorithm for All-Terminal Network Reliability
- Concentration of Lipschitz Functionals of Determinantal and Other Strong Rayleigh Measures
- The Random-Cluster Model
- Mathematical Foundations of Computer Science 2005
- Optimal mixing of Glauber dynamics: entropy factorization via high-dimensional expansion
- Log-concave polynomials IV: approximate exchange, tight mixing times, and near-optimal sampling of forests
This page was built for publication: Log-concave polynomials. II: High-dimensional walks and an FPRAS for counting bases of a matroid
