EUVIMEDOdkrijte EUVIMED
Crossref

Approximating permanents and hafnians

Alexander Barvinok

Discrete Analysis · 2017

DOI: 10.19086/da.1244 ↗

At a glance

Journal article in Discrete Analysis, 2017. Written by Alexander Barvinok. Cited 7 times so far (Crossref).

AbstraktBibliografické údajeCiteRelated studies

Abstract (original language)

We prove that the logarithm of the permanent of an nxn real matrix A and the logarithm of the hafnian of a 2nx2n real symmetric matrix A can be approximated within an additive error 1 > epsilon > 0 by a polynomial p in the entries of A of degree O(ln n - ln epsilon) provided the entries a_ij of A satisfy delta 0, fixed in advance. Moreover, the polynomial p can be computed in n^{O(ln n - ln epsilon)} time. We also improve bounds for approximating ln per A, ln haf A and logarithms of multi-dimensional permanents for complex matrices and tensors A.

Cite

APA

Barvinok, A. (2017). Approximating permanents and hafnians. Discrete Analysis. https://doi.org/10.19086/da.1244

Vancouver

Barvinok A. Approximating permanents and hafnians. Discrete Analysis. 2017. doi:10.19086/da.1244

BibTeX
@article{Barvinok2017,
  author = {Barvinok, Alexander},
  title = {Approximating permanents and hafnians},
  journal = {Discrete Analysis},
  year = {2017},
  doi = {10.19086/da.1244}
}
Start for free →