{"id":"openai-math/A-Fully-Polynomial-Randomized-Approximation-Scheme-for-Perfect-Matchings-in-General-Graphs","pdf":"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","url":"https://github.com/openai/math/tree/main/preprints/A-Fully-Polynomial-Randomized-Approximation-Scheme-for-Perfect-Matchings-in-General-Graphs-September-23-2026","tags":["approximate-counting","perfect-matchings","randomized-algorithms"],"score":0,"title":"A Fully Polynomial Randomized Approximation Scheme for Perfect Matchings in General Graphs","domain":"Theoretical computer science","family":"113","origin":"ai-generated","source":"openai-math","authors":["OpenAI"],"reviews":0,"subject":"cs.CC","summary":"We give a fully polynomial randomized approximation scheme (FPRAS) for counting perfect matchings in arbitrary finite simple undirected graphs, resolving the general-graph perfect-matching approximation problem. The algorithm returns zero with certainty when no perfect matching exists. Otherwise, it achieves relative error ε with failure probability at most δ in worst-case bit time polynomial in the input length, $`\\varepsilon ^{-1}`$, and $`\\log\\delta^{-1}`$.","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":1,"published":"2026-09-23","reactions":{},"discussion":[{"url":"https://arxiv.org/abs/2610.26803","date":"2026-10-19","kind":"web","site":"arXiv.org","text":"We give a simplified, self-contained proof of OpenAI's FPRAS for counting perfect matchings in general graphs. As in the original proof, we use a restricted Poincaré inequality for two matchings to sample weighted perfect matchings and estimate their total weight. We simplify the proof of this…","added":"2026-10-24","title":"A simplified proof of the FPRAS for counting perfect matchings","author":"Chenghua Liu, Boning Meng","record":"arxiv/2610.26803"}],"formalized":false,"family_title":"Approximate counting and entropy of perfect matchings"}