Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with stable :
TR13-141 | 8th October 2013
Leonid Gurvits

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

Revisions: 1

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 with
boolean matrices with prescribed row and (uniformly bounded) column sums within simply ... more >>>

ISSN 1433-8092 | Imprint