Low rank approximations of symmetric polynomials and asymptotic counting of contingency tables

Mathematics – Combinatorics

Scientific paper

Rate now

  [ 0.00 ] – not rated yet Voters 0   Comments 0

Details

16 pages

Scientific paper

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.

No associations

LandOfFree

Say what you really think

Search LandOfFree.com for scientists and scientific papers. Rate them and share your experience with other people.

Rating

Low rank approximations of symmetric polynomials and asymptotic counting of contingency tables does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Low rank approximations of symmetric polynomials and asymptotic counting of contingency tables, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Low rank approximations of symmetric polynomials and asymptotic counting of contingency tables will most certainly appreciate the feedback.

Rate now

     

Profile ID: LFWR-SCP-O-369695

  Search
All data on this website is collected from public sources. Our data reflects the most accurate information available at the time of publication.