@article{Edmonds1965, author = {Edmonds, Jack}, title = {Maximum Matching and a Polyhedron with {0,1}-Vertices}, journal = {Journal of Research of the National Bureau of Standards, Section B}, volume = {69B}, number = {1--2}, pages = {125--130}, year = {1965}, doi = {10.6028/jres.069B.013}, url = {https://nvlpubs.nist.gov/nistpubs/jres/69B/jresv69Bn1-2p125_A1b.pdf} } @article{Valiant1979, author = {Valiant, Leslie G.}, title = {The Complexity of Computing the Permanent}, journal = {Theoretical Computer Science}, volume = {8}, number = {2}, pages = {189--201}, year = {1979}, doi = {10.1016/0304-3975(79)90044-6}, url = {https://www.cs.bu.edu/faculty/gacs/courses/cs535/papers/Valiant_permanent.pdf} } @article{Barvinok1999, author = {Barvinok, Alexander}, title = {Polynomial Time Algorithms to Approximate Permanents and Mixed Discriminants Within a Simply Exponential Factor}, journal = {Random Structures \& Algorithms}, volume = {14}, number = {1}, pages = {29--61}, year = {1999}, doi = {10.1002/(SICI)1098-2418(1999010)14:1<29::AID-RSA2>3.0.CO;2-X}, note = {Section locator refers to the author preprint}, url = {https://sites.lsa.umich.edu/barvinok/wp-content/uploads/sites/1434/2025/05/permanent.pdf} } @article{LinialSamorodnitskyWigderson2000, author = {Linial, Nathan and Samorodnitsky, Alex and Wigderson, Avi}, title = {A Deterministic Strongly Polynomial Algorithm for Matrix Scaling and Approximate Permanents}, journal = {Combinatorica}, volume = {20}, number = {4}, pages = {545--568}, year = {2000}, doi = {10.1007/s004930070007}, note = {Theorem locator refers to the author version}, url = {https://www.math.ias.edu/~avi/PUBLICATIONS/MYPAPERS/LSW98/lsw00.pdf} } @article{JerrumSinclairVigoda2004, author = {Jerrum, Mark and Sinclair, Alistair and Vigoda, Eric}, title = {A Polynomial-Time Approximation Algorithm for the Permanent of a Matrix with Nonnegative Entries}, journal = {Journal of the ACM}, volume = {51}, number = {4}, pages = {671--697}, year = {2004}, doi = {10.1145/1008731.1008738}, url = {https://doi.org/10.1145/1008731.1008738} } @article{Barvinok2017, author = {Barvinok, Alexander}, title = {Approximating Permanents and Hafnians}, journal = {Discrete Analysis}, year = {2017}, volume = {2017}, number = {2}, pages = {1--34}, doi = {10.19086/da.1244}, url = {https://discreteanalysisjournal.com/article/1244-approximating-permanents-and-hafnians}, eprint = {1601.07518v5}, archivePrefix = {arXiv}, primaryClass = {math.CO}, note = {Theorem locator refers to the final arXiv version 1601.07518v5, 13 January 2017} } @inproceedings{AnariOveisGharanVinzant2018, author = {Anari, Nima and Oveis Gharan, Shayan and Vinzant, Cynthia}, title = {Log-Concave Polynomials, Entropy, and a Deterministic Approximation Algorithm for Counting Bases of Matroids}, booktitle = {2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS)}, pages = {35--46}, publisher = {IEEE}, year = {2018}, doi = {10.1109/FOCS.2018.00013}, url = {https://ieee-focs.org/FOCS-2018-Papers/pdfs/59f035.pdf} } @article{PadbergRao1982, author = {Padberg, Manfred W. and Rao, M. R.}, title = {Odd Minimum Cut-Sets and {$b$}-Matchings}, journal = {Mathematics of Operations Research}, volume = {7}, number = {1}, pages = {67--80}, year = {1982}, doi = {10.1287/moor.7.1.67}, url = {https://pubsonline.informs.org/doi/10.1287/moor.7.1.67} } @article{Jaynes1957, author = {Jaynes, Edwin T.}, title = {Information Theory and Statistical Mechanics}, journal = {Physical Review}, volume = {106}, number = {4}, pages = {620--630}, year = {1957}, doi = {10.1103/PhysRev.106.620}, url = {https://doi.org/10.1103/PhysRev.106.620} } @inproceedings{SinghVishnoi2014, author = {Singh, Mohit and Vishnoi, Nisheeth K.}, title = {Entropy, Optimization and Counting}, booktitle = {Proceedings of the Forty-Sixth Annual ACM Symposium on Theory of Computing}, pages = {50--59}, publisher = {ACM}, year = {2014}, doi = {10.1145/2591796.2591803}, note = {Full version arXiv:1304.8108v1, 2013}, url = {https://arxiv.org/abs/1304.8108v1} } @article{AbdiCornuejolsDadushDalirrooyfard2026, author = {Abdi, Ahmad and Cornu{\'e}jols, G{\'e}rard and Dadush, Daniel and Dalirrooyfard, Mahsa}, title = {Lower bounds for cube-ideal set-systems}, journal = {Proceedings of the London Mathematical Society}, volume = {133}, number = {2}, pages = {e70199}, year = {2026}, doi = {10.1112/plms.70199}, url = {https://londmathsoc.onlinelibrary.wiley.com/doi/10.1112/plms.70199} } @article{EsperetEtAl2011, author = {Esperet, Louis and Kardo{\v{s}}, Franti{\v{s}}ek and King, Andrew D. and Kr{\'a}{\v{l}}, Daniel and Norine, Serguei}, title = {Exponentially Many Perfect Matchings in Cubic Graphs}, journal = {Advances in Mathematics}, volume = {227}, number = {4}, pages = {1646--1664}, year = {2011}, doi = {10.1016/j.aim.2011.03.015}, url = {https://arxiv.org/abs/1012.2878v2}, note = {Numbered statements refer to arXiv:1012.2878v2, 5 September 2011, whose exposition differs from the journal version} } @inproceedings{EbrahimnejadEtAl2021, author = {Ebrahimnejad, Farzam and Nagda, Ansh and {Oveis Gharan}, Shayan}, title = {Counting and Sampling Perfect Matchings in Regular Expanding Non-Bipartite Graphs}, booktitle = {13th Innovations in Theoretical Computer Science Conference}, series = {Leibniz International Proceedings in Informatics}, volume = {215}, pages = {61:1--61:12}, year = {2022}, doi = {10.4230/LIPIcs.ITCS.2022.61}, url = {https://arxiv.org/abs/2103.08683v1}, note = {Conjecture locator refers to arXiv:2103.08683v1, 15 March 2021} } @misc{DongJain2026, author = {Dong, Dingding and Jain, Vishesh}, title = {A deterministic {$(1+\varepsilon)^n$} approximation for the permanent of a nonnegative matrix}, year = {2026}, eprint = {2609.11049}, archivePrefix = {arXiv}, note = {Version 1}, url = {https://arxiv.org/abs/2609.11049v1} } @misc{KudriaLuoMajid2026, author = {Kudria, Sergei and Luo, Jason and Majid, Mahbod}, title = {Subexponential Approximation of the Permanent in Deterministic Polynomial Time}, year = {2026}, eprint = {2609.10516}, archivePrefix = {arXiv}, note = {Version 1}, url = {https://arxiv.org/abs/2609.10516v1} } @misc{Yi2026, author = {Yi, Zihong}, title = {Diffuse {Gaussian} Truncation for Deterministic Approximate Counting}, year = {2026}, eprint = {2609.04079}, archivePrefix = {arXiv}, note = {Version 1}, url = {https://arxiv.org/abs/2609.04079v1} } @inproceedings{SvenssonTarnawski2017, author = {Svensson, Ola and Tarnawski, Jakub}, title = {The matching problem in general graphs is in {Quasi-NC}}, booktitle = {2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS)}, pages = {696--707}, publisher = {IEEE}, year = {2017}, doi = {10.1109/FOCS.2017.70}, url = {https://doi.org/10.1109/FOCS.2017.70}, note = {Full version: arXiv:1704.01929v2, 4 September 2017} } @article{WainwrightJordan2008, author = {Wainwright, Martin J. and Jordan, Michael I.}, title = {Graphical Models, Exponential Families, and Variational Inference}, journal = {Foundations and Trends in Machine Learning}, volume = {1}, number = {1--2}, pages = {1--305}, year = {2008}, doi = {10.1561/2200000001}, url = {https://doi.org/10.1561/2200000001} } @article{ChungGrahamFranklShearer1986, author = {Chung, Fan R. K. and Graham, Ronald L. and Frankl, Peter and Shearer, James B.}, title = {Some Intersection Theorems for Ordered Sets and Graphs}, journal = {Journal of Combinatorial Theory, Series A}, volume = {43}, number = {1}, pages = {23--37}, year = {1986}, doi = {10.1016/0097-3165(86)90019-1}, url = {https://www.renyi.hu/~pfrankl/j32.pdf} } @article{Schrijver1998Counting, author = {Schrijver, Alexander}, title = {Counting 1-Factors in Regular Bipartite Graphs}, journal = {Journal of Combinatorial Theory, Series B}, year = {1998}, volume = {72}, number = {1}, pages = {122--135}, month = jan, doi = {10.1006/jctb.1997.1798}, url = {https://doi.org/10.1006/jctb.1997.1798} } @techreport{Gurvits2011SchrijverBethe, author = {Gurvits, Leonid}, title = {Unleashing the power of {Schrijver}'s permanental inequality with the help of the {Bethe} Approximation}, institution = {Electronic Colloquium on Computational Complexity}, type = {ECCC Report}, number = {TR11-169}, year = {2011}, url = {https://eccc.weizmann.ac.il/report/2011/169/}, eprint = {1106.2844v11}, archivePrefix = {arXiv}, primaryClass = {math.CO}, note = {Expanded version: arXiv:1106.2844v11 (20 June 2012)} } @article{CyganPilipczukSkrekovski2013, author = {Cygan, Marek and Pilipczuk, Marcin and {\v{S}}krekovski, Riste}, title = {A bound on the number of perfect matchings in {Klee}-graphs}, journal = {Discrete Mathematics \& Theoretical Computer Science}, year = {2013}, volume = {15}, number = {1}, pages = {37--52}, month = jan, doi = {10.46298/dmtcs.633}, url = {https://dmtcs.episciences.org/633}, issn = {1365-8050} } @article{FordFulkerson1957, author={Ford, Jr., L. R. and Fulkerson, D. R.}, title={A Simple Algorithm for Finding Maximal Network Flows and an Application to the {Hitchcock} Problem}, journal={Canadian Journal of Mathematics}, volume={9}, pages={210--218}, year={1957}, doi={10.4153/CJM-1957-024-0}, url={https://doi.org/10.4153/CJM-1957-024-0} } @article{Polyak1967, author={Polyak, B. T.}, title={A general method for solving extremal problems}, journal={Doklady Akademii Nauk SSSR}, volume={174}, number={1}, pages={33--36}, year={1967}, note={In Russian; method citation refers to Equation (1)}, url={https://www.mathnet.ru/eng/dan33049} } @misc{OpenAIMatchingFPRAS2026, author = {{OpenAI}}, title = {{A Fully Polynomial Randomized Approximation Scheme for Perfect Matchings in General Graphs}}, howpublished = {OpenAI Math Release preprint \href{https://github.com/openai/math/blob/main/preprints/A-Fully-Polynomial-Randomized-Approximation-Scheme-for-Perfect-Matchings-in-General-Graphs-September-23-2026/main.pdf}{OAI:A-Fully-Polynomial-Randomized-Approximation-Scheme-for-Perfect-Matchings-in-General-Graphs-September-23-2026}}, year = {2026} } @article{Naddef1982, author = {Naddef, Denis}, title = {Rank of Maximum Matchings in a Graph}, journal = {Mathematical Programming}, volume = {22}, pages = {52--70}, year = {1982}, doi = {10.1007/BF01581025}, url = {https://doi.org/10.1007/BF01581025} } @article{EdmondsPulleyblankLovasz1982, author = {Edmonds, Jack and Pulleyblank, William R. and Lov{\'a}sz, L{\'a}szl{\'o}}, title = {Brick Decompositions and the Matching Rank of Graphs}, journal = {Combinatorica}, volume = {2}, number = {3}, pages = {247--274}, year = {1982}, doi = {10.1007/BF02579233}, url = {https://doi.org/10.1007/BF02579233} }