Computing the permanent of (some) complex matrices

Alexander Barvinok

RECORD

Computing the permanent of (some) complex matrices

Alexander Barvinok

Combinatorics · Submitted 6 May 2014

abstract compiled · 2026-09-23 · no language-model review

The authors' main claim We present a deterministic algorithm, which, for any given 0< epsilon < 1 and an nxn real or complex matrix A=(a_{ij}) such that | a_{ij}-1| < 0.19 for all i, j computes the permanent of A within relative error epsilon in n^{O(ln n -ln epsilon)} time.

how it is stated · asserted 1.00 read the record →

Comment (0) Read on arXiv ↗

Cite ▾

Claim paper

The compiled record

The paper's own sentences, arranged. Each label is drawn from a closed vocabulary; the number beside it is the probability the classifier gave that label. Numbers in the tables are the authors', checked by code. No sentence in this record was written by a model.

Open the compiled record

Compiled by classifier-1.13-20260917 via OpenRouter, question bank abstract-p1-20260923, 2026-09-23: 1 request, 2,360 input tokens, $0.0001 reported.

What the abstract itself states, as probabilities: claims first 0.04 · states limitation 0.79 · human participants 0.01 · controlled comparison 0.01 · randomized assignment 0.01 · states quantitative result 0.98 · compares with prior results 0.06 · mentions code or data availability 0.02.

The abstract, sentence by sentence

arXiv listing abstract v2. Results and the main claim are underlined; show every role.

We present a deterministic algorithm, which, for any given 0< epsilon < 1 and an nxn real or complex matrix A=(a_{ij}) such that | a_{ij}-1| < 0.19 for all i, j computes the permanent of A within relative error epsilon in n^{O(ln n -ln epsilon)} time. The method can be extended to computing hafnians and multidimensional permanents.

background contribution method result interpretation main claim

What the classifier reports for each sentence. The number is the probability it gave the label.
#	sentence	role	the authors' own work	states the main conclusion	strength
s0	We present a deterministic algorithm, which, for any given 0< epsilon < 1 and an nxn real or complex matrix A=(a_{ij}) such that \| a_{ij}-1\| < 0.19 for all i, j computes the permanent of A within relative error epsilon in n^{O(ln n -ln epsilon)} time.	contribution 0.96	0.94	0.86	asserted 1.00
s1	The method can be extended to computing hafnians and multidimensional permanents.	contribution 0.62	0.77	0.06	hedged possibility 0.63

What kind of paper the classifier reports this is: method or tool 0.98 · evidence from proof or derivation 1.00.

What was examined, and what was not

sources read

arXiv listing abstract v2

not examined

full text
figures and tables
references and citing sentences
relations to other papers

levels run

P abstract

not run

S sections
T body sentences
C citations
R cross-paper relations

Every quoted sentence on this record is the authors'. Every label is from Pith's closed vocabulary, with the probability shown beside it. Every number in the measurements table is the authors', checked by code. Record as JSON

The paper

Original abstract

We present a deterministic algorithm, which, for any given 0< epsilon < 1 and an nxn real or complex matrix A=(a_{ij}) such that | a_{ij}-1| < 0.19 for all i, j computes the permanent of A within relative error epsilon in n^{O(ln n -ln epsilon)} time. The method can be extended to computing hafnians and multidimensional permanents.

Human review

How Pith checks papers → · Full audit of this paper →

How the literature uses it

5 arXiv papers cite this in 8 sentences

Each citing sentence is taken from the citing paper's LaTeX source and typed by Pith's classifier. A label appears at probability 0.8 or more (0.95 for support), a contest at 0.7 or more; the quoted words are the citing authors'. How each label was checked · JSON

Papers citing it · 4 sentences without a confident label

Uses its method or tool 1 paper

Our algorithm is based on an approach due to Barvinok [ref] for approximating evaluations of a polynomial based on the location of the complex zeros and a technique due to Patel and Regts [ref] for efficiently computing the leading coefficients of graph polynomials on bounded degree graphs.

Approximation Algorithms for Complex-Valued Ising Models on Bounded Degree Graphs · Introduction · 0.98

Cites it as background 1 paper

Recent works of Barvinok [ref] have outlined a new approach to computing the permanent, and in fact a large class of high-degree polynomials in matrices such as the partition function [ref] .

Approximating the Permanent of a Random Matrix with Vanishing Mean · A complex function perspective · 0.90

Discussion

Know something about this paper? Leave a comment, or highlight any passage above to comment on it.