Real Stable Polynomials and Matroids: Optimization and Counting
Straszak, Vishnoi · cs.DS,math.CO,math.OC,math.PR · 2016-11-14 · 原文
A great variety of fundamental optimization and counting problems arising in computer science, mathematics and physics can be reduced to one of the following computational tasks involving polynomials and set systems: given an m-variate real polynomial g and a family of subsets B of [m], (1) find S\in B such that the monomial in g corresponding to S has the largest coefficient in g, or (2) compute the sum of coefficients of monomials in g corresponding to all the sets in B. Special cases of these problems, such as computing permanents, sampling from DPPs and maximizing subdeterminants have been topics of recent interest in theoretical computer science. In this paper we present a general convex programming framework geared to solve both of these problems. We show that roughly, when g is a real stable polynomial with non-negative coefficients and B is a matroid, the integrality gap of our relaxation is finite and depends only on m (and not on the coefficients of g). Prior to our work, such results were known only in sporadic cases that relied on the structure of g and B; it was not even clear if one could formulate a convex relaxation that has a finite in
讲义
讲义·推断 依据「原文」自动生成的结构化摘要（推断），非原文表述；以原文为准。
1. 人话版
A great variety of fundamental optimization and counting problems arising in computer science, mathematics and physics can be reduced to one of the following computational tasks involving polynomials and set systems: given an m-variate real polynomial g and a family of subsets B of [m], (1) find S\in B such that the monomial in g corresponding to S has the largest coefficient in g, or (2) compute the sum of coefficients of monomials in g corresponding to all the sets in B.
Special cases of these problems, such as computing permanents, sampling from DPPs and maximizing subdeterminants have been topics of recent interest in theoretical computer science.
2. 领域脉络
本文类目：cs.DS、math.CO、math.OC、math.PR，属于其所在研究脉络的最新进展。
3. 机制拆解
In this paper we present a general convex programming framework geared to solve both of these problems.
4. 证据与数字
摘要未给出量化结果——留意原文的实验与数据。
5. 反例与边界
We show that roughly, when g is a real stable polynomial with non-negative coefficients and B is a matroid, the integrality gap of our relaxation is finite and depends only on m (and not on the coefficients of g).
Prior to our work, such results were known only in sporadic cases that relied on the structure of g and B; it was not even clear if one could formulate a convex relaxation that has a finite in
6. 跨领域连接与意外收获
横跨 4 个类目（cs.DS、math.CO、math.OC、math.PR），关注其在你兴趣板块间的迁移面。
7. 可复用方法
把本文机制与你手头项目对照，找一个两周内能验证的最小实验。
8. 术语表
精读时把不熟的术语记入此处，作为下次回忆的锚点。