Log-concave polynomials. I: Entropy and a deterministic approximation algorithm for counting bases of matroids
From MaRDI portal
Publication:2059021
DOI10.1215/00127094-2020-0091OpenAlexW3207601372MaRDI QIDQ2059021
Nima Anari, Cynthia Vinzant, Shayan Oveis Gharan
Publication date: 13 December 2021
Published in: Duke Mathematical Journal (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1807.00929
convex programmingmatroidsmatroid intersectionapproximate countingcombinatorial Hodge theorylog-concave polynomials
Convex programming (90C25) Combinatorial aspects of matroids and geometric lattices (05B35) Approximation algorithms (68W25)
Related Items
Counting matchings via capacity-preserving operators ⋮ Maximum entropy and integer partitions ⋮ Paving property for real stable polynomials and strongly Rayleigh processes ⋮ Logarithmic concavity for morphisms of matroids ⋮ Modified log-Sobolev inequalities for strong-Rayleigh measures ⋮ The work of June Huh ⋮ Blowup polynomials and delta-matroids of graphs ⋮ Log-concave polynomials. II: High-dimensional walks and an FPRAS for counting bases of a matroid ⋮ Lorentzian polynomials, Segre classes, and adjoint polynomials of convex polyhedral cones ⋮ Combinatorics and Hodge theory ⋮ Combinatorial Bernoulli factories ⋮ Lower bounds for contingency tables via Lorentzian polynomials ⋮ Topology of real multi-affine hypersurfaces and a homological stability property ⋮ Pfaffian pairs and parities: counting on linear matroid intersection and parity problems ⋮ Log concavity and concentration of Lipschitz functions on the Boolean hypercube ⋮ Pfaffian Pairs and Parities: Counting on Linear Matroid Intersection and Parity Problems ⋮ A Tight Analysis of Bethe Approximation for Permanent
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Two remarks concerning balanced matroids
- Random weighting, asymptotic counting, and inverse isoperimetry
- A polynomial-time algorithm to approximate the mixed volume within a simply exponential factor
- Testing membership in matroid polyhedra
- Approximate counting, uniform generation and rapidly mixing Markov chains
- On the problem of approximating the number of bases of a matroid
- Homogeneous multivariate polynomials with the half-plane property
- Hodge theory for combinatorial geometries
- Enumeration of points, lines, planes, etc.
- Elementary bounds on Poincaré and log-Sobolev constants for decomposable Markov chains
- Combinatorial optimization. Polyhedra and efficiency (3 volumes)
- Counting bases of representable matroids
- Simplicial generation of Chow rings of matroids
- Lorentzian polynomials
- Interlacing families. I: Bipartite Ramanujan graphs of all degrees
- Interlacing families. II: Mixed characteristic polynomials and the Kadison-Singer problem
- Polynomials with the half-plane property and matroid theory
- Hyperbolic polynomials approach to Van der Waerden/Schrijver-Valiant like conjectures
- A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries
- Hyperbolic Polynomials and Interior Point Methods for Convex Programming
- Real stable polynomials and matroids: optimization and counting
- A generalization of permanent inequalities and applications in counting and optimization
- Log-concave polynomials II: high-dimensional walks and an FPRAS for counting bases of a matroid
- Entropy, optimization and counting
- Maximizing determinants under partition constraints
- Elements of Information Theory
- A Randomized Rounding Approach to the Traveling Salesman Problem
- Matroids and the greedy algorithm
- Combinatorial and geometric approaches to counting problems on linear matroids, graphic arrangements, and partial orders
