research-article

Public Access

Log-concave polynomials II: high-dimensional walks and an FPRAS for counting bases of a matroid

Authors:

Shayan Oveis Gharan,

Cynthia VinzantAuthors Info & Claims

STOC 2019: Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing

Pages 1 - 12

https://doi.org/10.1145/3313276.3316385

Published: 23 June 2019 Publication History

Abstract

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 estimate 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 edge expansion at least 1.

Our algorithm and proof build on the recent results of Dinur, Kaufman, Mass and Oppenheim who show that a high dimensional walk on a weighted simplicial complex mixes rapidly if for every link of the complex, the corresponding localized random walk on the 1-skeleton is a strong spectral expander. One of our key observations is that a weighted simplicial complex X is a 0-local spectral expander if and only if a naturally associated generating polynomial p_X is strongly log-concave. More generally, to every pure simplicial complex with positive weights on its maximal faces, we can associate to X a multiaffine homogeneous polynomial p_X such that the eigenvalues of the localized random walks on X correspond to the eigenvalues of the Hessian of derivatives of p_X.

References

[1]

{AHK18} Karim Adiprasito, June Huh, and Eric Katz. “Hodge theory for combinatorial geometries”. In: Annals of Mathematics 188.2 (2018), pp. 381– 452. {Alo86} N Alon. “Eigenvalues and expanders”. In: Combinatorica 6 (2 Jan. 1986), pp. 83–96. issn: 0209-9683.

Digital Library

[2]

{AM85} N. Alon and V. Milman. “Isoperimetric inequalities for graphs, and superconcentrators”. In: Journal of Combinatorial Theory, Series B 38.1 (Feb. 1985), pp. 73–88. {Ana+18a} Nima Anari, Kuikui Liu, Shayan Oveis Gharan, and Cynthia Vinzant. “Log-Concave Polynomials II: High-Dimensional Walks and an FPRAS for Counting Bases of a Matroid”. In: arXiv preprint arXiv:1811.01816 (2018).

[3]

{Ana+18b} Nima Anari, Kuikui Liu, Shayan Oveis Gharan, and Cynthia Vinzant. “Log-Concave Polynomials III: Mason’s Ultra-Log-Concavity Conjecture for Independent Sets of Matroids”. In: arXiv preprint arXiv:1811.01600 (2018).

[4]

{AOR16} Nima Anari, Shayan Oveis Gharan, and Alireza Rezaei. “Monte Carlo Markov Chain Algorithms for Sampling Strongly Rayleigh Distributions and Determinantal Point Processes”. In: COLT. 2016, pp. 103–115.

[5]

{AOV18} Nima Anari, Shayan Oveis Gharan, and Cynthia Vinzant. “Log-concave polynomials, entropy, and a deterministic approximation algorithm for counting bases of matroids”. In: FOCS. to appear. 2018.

[6]

{BH18} Petter Brändén and June Huh. “Hodge-Riemann relations for Potts model partition functions”. In: arXiv preprint arXiv:1811.01696 (2018).

[7]

{BH19} Petter Brändén and June Huh. “Lorentzian polynomials”. In: arXiv preprint arXiv:1902.03719 (2019).

[8]

{BS07} Alexander Barvinok and Alex Samorodnitsky. “Random weighting, asymptotic counting, and inverse isoperimetry”. In: Israel Journal of Mathematics 158.1 (Mar. 2007), pp. 159–191. issn: 1565-8511.

[9]

{BŚ97} W. Ballmann and J. Światkowski. “On L2-cohomology and property (T) for automorphism groups of polyhedral cell complexes”. In: Geom. Funct. Anal. 7.4 (1997), pp. 615–645. {Clo10} Brian D. Cloteaux. “Approximating the Number of Bases for Almost All Matroids”. In: Congressus Numerantium 202 (2010), pp. 149–154.

[10]

{CTY15} Emma Cohen, Prasad Tetali, and Damir Yeliussizov. “Lattice path matroids: negative correlation and fast mixing”. In: arXiv preprint arXiv:1505.06710 (2015).

[11]

{DK17} I. Dinur and T. Kaufman. “High Dimensional Expanders Imply Agreement Expanders”. In: FOCS. 2017, pp. 974–985.

[12]

{DS91} Persi Diaconis and Daniel Stroock. “Geometric bounds for eigenvalues of Markov chains”. In: The Annals of Applied Probability (1991), pp. 36– 61.

[13]

{FK72} Cornelis Marius Fortuin and Pieter Willem Kasteleyn. “On the randomcluster model: I. Introduction and relation to other models”. In: Physica 57 (4 1972), pp. 536–564.

[14]

{FM92} Tomás Feder and Milena Mihail. “Balanced matroids”. In: STOC. 1992, pp. 26–38. {For71} Cornelis Marius Fortuin. “On the random-cluster model”. PhD thesis. Leiden University, 1971.

Digital Library

[15]

{For72a} Cornelis Marius Fortuin. “On the random-cluster model: II. The percolation model”. In: Physica 58 (3 1972), pp. 393–418. {For72b} Cornelis Marius Fortuin. “On the random-cluster model: III. The simple random-cluster model”. In: Physica 59 (4 1972), pp. 545–570. {Gam99} Anna Gambin. “On approximating the number of bases of exchange preserving matroids”. In: International Symposium on Mathematical Foundations of Computer Science. Springer. 1999, pp. 332–342. {Gar73} H. Garland. “p-adic curvature and the cohomology of discrete subgroups of p-adic groups”. In: Annals of Mathematics 97.3 (1973), pp. 375–423.

Digital Library

[16]

{GJ08} L. A. Goldberg and M. Jerrum. “Inapproximability of the Tutte polynomial”. In: Inform. and Comput 206.7 (2008), pp. 908–929. {GJ12a} L. A. Goldberg and M. Jerrum. “Approximating the partition function of the ferromagnetic Potts model”. In: J. ACM 59.5 (2012), pp. 1–31. {GJ12b} L. A. Goldberg and M. Jerrum. “Inapproximability of the Tutte polynomial of a planar graph”. In: Computational Complexity 21 (4 2012), pp. 605–642.

Digital Library

[17]

{GJ13} L. A. Goldberg and M. Jerrum. “Approximating the Tutte polynomial of a binary matroid and other related combinatorial polynomials”. In: Journal of Computer and System Sciences 79 (1 2013), pp. 68–78.

Digital Library

[18]

{GJ14} L. A. Goldberg and M. Jerrum. “The complexity of computing the sign of the Tutte polynomial”. In: SIAM J. Comput. 43 (2014), pp. 1921–1952.

[19]

{GJ17} Heng Guo and Mark Jerrum. “Random cluster dynamics for the Ising model is rapidly mixing”. In: SODA. 2017, pp. 1818–1827.

Digital Library

[20]

{GJ18a} Heng Guo and Mark Jerrum. “A Polynomial-Time Approximation Algorithm for All-Terminal Network Reliability”. In: ICALP. 2018, 68:1– 68:12. {GJ18b} Heng Guo and Mark Jerrum. “Approximately counting bases of bicircular matroids”. 2018.

[21]

{Gri09} G. R Grimmett. The Random-Cluster Model. Berlin: Springer-Verlag, 2009.

[22]

{Gur09} Leonid Gurvits. “A polynomial-time algorithm to approximate the mixed volume within a simply exponential factor”. In: Discrete & Computational Geometry 41.4 (2009), pp. 533–555. {Gur10} Leonid Gurvits. “On multivariate Newton-like inequalities”. In: Advances in Combinatorial Mathematics. Berlin, Heidelberg: Springer Berlin Heidelberg, 2010, pp. 61–78.

Digital Library

[23]

{HJ13} Roger A Horn and Charles R Johnson. Matrix analysis. 2nd ed. Cambridge university press, 2013.

[24]

{HW16} June Huh and Botong Wang. “Enumeration of points, lines, planes, etc”. In: arXiv preprint arXiv:1609.05484 (2016).

[25]

{Jer+04} Mark Jerrum, Jung-Bae Son, Prasad Tetali, and Eric Vigoda. “Elementary bounds on Poincaré and log-Sobolev constants for decomposable Markov chains”. In: Annals of Applied Probability (2004), pp. 1741–1765.

[26]

{Jer06} Mark Jerrum. “Two Remarks Concerning Balanced Matroids”. In: Combinatorica 26.6 (2006), pp. 733–742.

Digital Library

[27]

{JS02} Mark Jerrum and Jung Bae Son. “Spectral gap and log-Sobolev constant for balanced matroids”. In: FOCS. 2002, pp. 721–729.

Digital Library

[28]

{JS93} Mark Jerrum and Alistair Sinclair. “Polynomial-time approximation algorithms for the Ising model”. In: SIAM J. Comput. 22.5 (1993), pp. 1087– 1116.

Digital Library

[29]

{JVV86} Mark Jerrum, Leslie Valiant, and Vijay Vazirani. “Random Generation of Combinatorial Structures from a Uniform Distribution”. In: Theoretical Computer Science 43 (1986), pp. 169–188.

[30]

{JVW90} F. Jaeger, D. L. Vertigan, and D. J. A. Welsh. “On the computational complexity of the Jones and Tutte polynomials”. In: Mathematical Proceedings of the Cambridge Philosophical Society 108 (1 1990), pp. 35– 53.

[31]

{KM17} Tali Kaufman and David Mass. “High Dimensional Random Walks and Colorful Expansion”. In: ITCS. 2017, 4:1–4:27.

[32]

{KO18} Tali Kaufman and Izhar Oppenheim. “High Order Random Walks: Beyond Spectral Gap”. In: APPROX/RANDOM. 2018, 47:1–47:17.

[33]

{KT12} Alex Kulesza and Ben Taskar. “Determinantal point processes for machine learning”. In: Foundations and Trends in Machine Learning 5(2-3) (2012), pp. 123–286. {Lub17} Alexander Lubotzky. “High Dimensional Expanders”. 2017.

[34]

{MS91} Milena Mihail and Madhu Sudan. Connectivity Properties of Matroids. Tech. rep. EECS Department, University of California, Berkeley, Dec. 1991.

[35]

{MV89} M. Mihail and U. Vazirani. “On the expansion of 0/1 polytopes”. In: Journal of Combinatorial Theory. B (1989).

[36]

{Opp18} Izhar Oppenheim. “Local spectral expansion approach to high dimensional expanders part I: Descent of spectral gaps”. In: Discrete and Computational Geometry 59.2 (2018), pp. 293–330. {Ver91} D.L. Vertigan. “On the computational complexity of tutte, jones, homfly and kauffman invariants”. PhD thesis. University of Oxford, 1991.

Digital Library

Cited By

Biyik EAnari NSadigh D(2024)Batch Active Learning of Reward Functions from Human PreferencesACM Transactions on Human-Robot Interaction10.1145/364988513:2(1-27)Online publication date: 14-Jun-2024
https://dl.acm.org/doi/10.1145/3649885
Chen XFeng WYin YZhang X(2024)Rapid Mixing of Glauber Dynamics via Spectral Independence for All DegreesSIAM Journal on Computing10.1137/22M1474734(FOCS21-224-FOCS21-298)Online publication date: 13-Jun-2024
https://doi.org/10.1137/22M1474734
Dikstein YHopkins M(2024)Chernoff Bounds and Reverse Hypercontractivity on HDX2024 IEEE 65th Annual Symposium on Foundations of Computer Science (FOCS)10.1109/FOCS61266.2024.00060(870-919)Online publication date: 27-Oct-2024
https://doi.org/10.1109/FOCS61266.2024.00060
Show More Cited By

Index Terms

Log-concave polynomials II: high-dimensional walks and an FPRAS for counting bases of a matroid
1. Mathematics of computing
  1. Discrete mathematics
    1. Graph theory
      1. Matroids and greedoids
2. Theory of computation
  1. Design and analysis of algorithms
  2. Randomness, geometry and discrete structures
    1. Generating random combinatorial structures
    2. Random walks and Markov chains

Recommendations

Fractionally log-concave and sector-stable polynomials: counting planar matchings and more
STOC 2021: Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing

We show fully polynomial time randomized approximation schemes (FPRAS) for counting matchings of a given size, or more generally sampling/counting monomer-dimer systems in planar, not-necessarily-bipartite, graphs. While perfect matchings on planar ...
Ehrhart Polynomials of Matroid Polytopes and Polymatroids

We investigate properties of Ehrhart polynomials for matroid polytopes, independence matroid polytopes, and polymatroids. In the first half of the paper we prove that, for fixed rank, Ehrhart polynomials of matroid polytopes and polymatroids are ...
Ehrhart Polynomials of Matroid Polytopes and Polymatroids

We investigate properties of Ehrhart polynomials for matroid polytopes, independence matroid polytopes, and polymatroids. In the first half of the paper we prove that, for fixed rank, Ehrhart polynomials of matroid polytopes and polymatroids are ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

STOC 2019: Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing

June 2019

1258 pages

ISBN:9781450367059

DOI:10.1145/3313276

General Chair:
Moses Charikar
Stanford University
,
Program Chair:
Edith Cohen
Google, USA / Tel Aviv University, Israel

Copyright © 2019 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 23 June 2019

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

Conference

STOC '19

Sponsor:

SIGACT

STOC '19: 51st Annual ACM SIGACT Symposium on the Theory of Computing

June 23 - 26, 2019

AZ, Phoenix, USA

Acceptance Rates

Overall Acceptance Rate 1,469 of 4,586 submissions, 32%

Upcoming Conference

STOC '25

Sponsor:
sigact

57th Annual ACM Symposium on Theory of Computing (STOC 2025)

June 23 - 27, 2025

Prague , Czech Republic

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

61
Total Citations
View Citations
1,456
Total Downloads

Downloads (Last 12 months)274
Downloads (Last 6 weeks)32

Reflects downloads up to 27 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Biyik EAnari NSadigh D(2024)Batch Active Learning of Reward Functions from Human PreferencesACM Transactions on Human-Robot Interaction10.1145/364988513:2(1-27)Online publication date: 14-Jun-2024
https://dl.acm.org/doi/10.1145/3649885
Chen XFeng WYin YZhang X(2024)Rapid Mixing of Glauber Dynamics via Spectral Independence for All DegreesSIAM Journal on Computing10.1137/22M1474734(FOCS21-224-FOCS21-298)Online publication date: 13-Jun-2024
https://doi.org/10.1137/22M1474734
Dikstein YHopkins M(2024)Chernoff Bounds and Reverse Hypercontractivity on HDX2024 IEEE 65th Annual Symposium on Foundations of Computer Science (FOCS)10.1109/FOCS61266.2024.00060(870-919)Online publication date: 27-Oct-2024
https://doi.org/10.1109/FOCS61266.2024.00060
Hafner EMészáros KVidinas A(2024)Log-Concavity of the Alexander PolynomialInternational Mathematics Research Notices10.1093/imrn/rnae0582024:13(10273-10284)Online publication date: 22-Apr-2024
https://doi.org/10.1093/imrn/rnae058
Pak I(2024)What is a combinatorial interpretation?Open Problems in Algebraic Combinatorics10.1090/pspum/110/02007(191-260)Online publication date: 2024
https://doi.org/10.1090/pspum/110/02007
Anari NLiu KOveis Gharan SVinzant C(2024)Log-concave polynomials III: Mason’s ultra-log-concavity conjecture for independent sets of matroidsProceedings of the American Mathematical Society10.1090/proc/16724Online publication date: 20-Mar-2024
https://doi.org/10.1090/proc/16724
Matsuoka TOhsaka N(2024)Computational Complexity of Normalizing Constants for the Product of Determinantal Point ProcessesTheoretical Computer Science10.1016/j.tcs.2024.114513(114513)Online publication date: Mar-2024
https://doi.org/10.1016/j.tcs.2024.114513
Dikstein YDinur IFilmus YHarsha P(2024)Boolean Function Analysis on High-Dimensional ExpandersCombinatorica10.1007/s00493-024-00084-544:3(563-620)Online publication date: 1-Jun-2024
https://dl.acm.org/doi/10.1007/s00493-024-00084-5
Nowak LO’Melveny PRoss D(2024)Mixed Volumes of Normal ComplexesDiscrete & Computational Geometry10.1007/s00454-024-00662-wOnline publication date: 4-Jun-2024
https://doi.org/10.1007/s00454-024-00662-w
Narayanan HShah RSrivastava N(2024)A Spectral Approach to Polytope DiameterDiscrete & Computational Geometry10.1007/s00454-024-00636-y72:4(1647-1674)Online publication date: 16-Mar-2024
https://doi.org/10.1007/s00454-024-00636-y
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Figures

Tables

Media

View Table of Conten