Geodesic
Approximating permanents and hafnians
Discrete analysis (2017)

Voir la notice de l'article provenant de la source Scholastica

arXiv
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 a_ij 1 for an arbitrarily small 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.
Publié le : 
Alexander Barvinok. Approximating permanents and hafnians. Discrete analysis (2017). http://geodesic.mathdoc.fr/item/DAS_2017_a18/
@article{DAS_2017_a18,
     author = {Alexander Barvinok},
     title = {Approximating permanents and hafnians},
     journal = {Discrete analysis},
     year = {2017},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DAS_2017_a18/}
}
TY  - JOUR
AU  - Alexander Barvinok
TI  - Approximating permanents and hafnians
JO  - Discrete analysis
PY  - 2017
UR  - http://geodesic.mathdoc.fr/item/DAS_2017_a18/
LA  - en
ID  - DAS_2017_a18
ER  - 
%0 Journal Article
%A Alexander Barvinok
%T Approximating permanents and hafnians
%J Discrete analysis
%D 2017
%U http://geodesic.mathdoc.fr/item/DAS_2017_a18/
%G en
%F DAS_2017_a18