Low rank approximations of symmetric polynomials and asymptotic counting of contingency tables
| dc.creator | Barvinok, Alexander | |
| dc.date | 2005-03-08 | |
| dc.date.accessioned | 2026-07-07T05:17:48Z | |
| dc.date.available | 2026-07-07T05:17:48Z | |
| dc.description | We represent the number of mxn non-negative integer matrices (contingency tables) with prescribed row sums and column sums as the expected value of the permanent of a non-negative random matrix with exponentially distributed entries. We bound the variance of the obtained estimator, from which it follows that if the row and column sums are bounded by a constant fixed in advance, we get a polynomial time approximation scheme for counting contingency tables. We show that the complete symmetric polynomial of a fixed degree in n variables can be epsilon-approximated coefficient-wise by a sum of powers of O(log n) linear forms, from which it follows that if the row sums (but not necessarily column sums) are bounded by a constant, there is a deterministic approximation algorithm of m^{O(log n)} complexity to compute the logarithmic asymptotic of the number of tables. | |
| dc.description | 16 pages | |
| dc.identifier | https://arxiv.org/abs/math/0503170 | |
| dc.identifier | http://arxiv.org/abs/math/0503170 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/74440 | |
| dc.subject | Combinatorics | |
| dc.subject | Optimization and Control | |
| dc.subject | 05A16, 68R05, 68W20, 15A15 | |
| dc.title | Low rank approximations of symmetric polynomials and asymptotic counting of contingency tables | |
| dc.type | text |