Name
Abstract | ||
|---|---|---|
We design a deterministic polynomial time cn approximation algorithm for the permanent of positive semidefinite matrices where c =
<sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">γ+1</sup>
≃ 4:84. We write a natural convex relaxation and show that its optimum solution gives a cn approximation of the permanent. We further show that this factor is asymptotically tight by constructing a family of positive semidefinite matrices. We also show that our result implies an approximate version of the permanent-ontop conjecture, which was recently refuted in its original form; we show that the permanent is within a cn factor of the top eigenvalue of the Schur power matrix. |
Year | DOI | Venue |
|---|---|---|
2017 | 10.1109/FOCS.2017.89 | 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS) |
Keywords | DocType | Volume |
permanent,positive semidefinite,permanent-ontop,approximation algorithm,semidefinite program,immanant | Conference | abs/1704.03486 |
ISSN | ISBN | Citations |
0272-5428 | 978-1-5386-3465-3 | 4 |
PageRank | References | Authors |
0.50 | 6 | 4 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Nima Anari | 1 | 79 | 14.83 |
| Leonid Gurvits | 2 | 43 | 3.31 |
| Shayan Oveis Gharan | 3 | 323 | 26.63 |
| Amin Saberi | 4 | 2824 | 224.27 |