  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 integrality gap beyond these special cases.
Two notable examples are a result by Gurvits on the van der Waerden conjecture
for real stable $g$ when $B$ is a single element and a result by Nikolov and
Singh for multilinear real stable polynomials when $B$ is a partition matroid.
Our work, which encapsulates most interesting cases of $g$ and $B$, benefits
from both - we were inspired by the latter in deriving the right convex
programming relaxation and the former in establishing the integrality gap.
However, proving our results requires significant extensions of both; in that
process we come up with new notions and connections between stable polynomials
and matroids which should be of independent interest.
