ECCC-Report TR13-141https://eccc.weizmann.ac.il/report/2013/141Comments and Revisions published for TR13-141en-usTue, 13 May 2014 00:35:05 +0300
Revision 1
| Boolean matrices with prescribed row/column sums and stable homogeneous polynomials: combinatorial and algorithmic applications |
Leonid Gurvits
https://eccc.weizmann.ac.il/report/2013/141#revision1We 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 oraclesTue, 13 May 2014 00:35:05 +0300https://eccc.weizmann.ac.il/report/2013/141#revision1
Paper TR13-141
| Boolean matrices with prescribed row/column sums and stable homogeneous polynomials: combinatorial and algorithmic applications |
Leonid Gurvits
https://eccc.weizmann.ac.il/report/2013/141We 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 oraclesTue, 08 Oct 2013 22:48:14 +0300https://eccc.weizmann.ac.il/report/2013/141