Boolean matrices with prescribed row/column sums and stable homogeneous polynomials: combinatorial and algorithmic applications

摘要

We prove a new efficiently computable lower bound on the coefficients of stable homogeneous polynomials and present its algorthmic and combinatorial applications. Our main application is the first poly-time deterministic algorithm which approximates the partition functions associated withboolean matrices with prescribed row and (uniformly bounded) column sums within simply exponential multiplicative factor. This new algorithm is a particular instance ofnew polynomial timedeterministic algorithms related to the multiple partial differentiation of polynomials given by evaluation oracles