Double-Cover-Based Analysis of the Bethe Permanent of Block-Structured Positive Matrices
We consider the permanent of a square matrix with non-negative entries. A tractable approximation is given by the so-called Bethe permanent that can be efficiently computed by running the sum-product algorithm on a suitable factor graph. While the ratio of the permanent of a matrix to its Bethe permanent is, in the worst case, upper and lower bounded by expressions that are exponentially far apart in the matrix size, in practice it is observed for many ensembles of matrices of interest that this ratio is strongly concentrated around some value that depends only on the matrix size. In this…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2601.17508
curl -X POST /api/v1/records/arxiv/2601.17508/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2601.17508/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'