Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
426420 | Information and Computation | 2015 | 14 Pages |
Abstract
We prove a new efficiently computable lower bound on the coefficients of stable homogeneous polynomials and present its algorithmic and combinatorial applications. Our main application is the first poly-time deterministic algorithm which approximates the partition functions associated with boolean matrices with prescribed row and column sums within simply exponential multiplicative factor. This new algorithm is a particular instance of new polynomial time deterministic algorithms related to the multiple partial differentiation of polynomials given by evaluation oracles.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Leonid Gurvits,