Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR13-141 | 13th May 2014 00:34

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

RSS-Feed




Revision #1
Authors: Leonid Gurvits
Accepted on: 13th May 2014 00:35
Downloads: 1252
Keywords: 


Abstract:

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 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



Changes to previous version:

A journal version, most of the typos are fixed.


Paper:

TR13-141 | 8th October 2013 21:24

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





TR13-141
Authors: Leonid Gurvits
Publication: 8th October 2013 22:48
Downloads: 3599
Keywords: 


Abstract:

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 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



ISSN 1433-8092 | Imprint