Papers for

statistical physics modelers

Papers whose findings have a practical use for this group, as judged from the abstract. Open a paper to read what it means in practice.

Deterministic algorithm estimates permanent of matrices efficiently

A deterministic $(1+\varepsilon)^n$ approximation for the permanent of a nonnegative matrix

Abstract: For every fixed $0<\varepsilon\le1$, we give a deterministic strongly polynomial algorithm that, given a nonnegative matrix $A\in\mathbb{R}_{\ge0}^{n\times n}$, returns $Q$ satisfying $\operatorname{per} A\le Q\le(1+\varepsilon)^n\operatorname{per} A$.

Thu 10 SeptData Structures and Algorithms
The gist
Calculating the permanent of a matrix is a hard math problem related to counting arrangements and patterns. The authors developed a reliable method that guesses the permanent value from a matrix without randomness. Their algorithm provides an estimate close to the real answer with error growing exponentially but controllably based on matrix size. It works efficiently and is predictable, helping in cases where previous approximations needed randomness.
Open → 2609.11049v1