Instruct: Identify the main and secondary category of Arxiv papers based on the titles and abstracts
Query: Real Stable Polynomials and Matroids: Optimization and Counting   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.

25
The categories of this paper are: patt-sol
29
The categories of this paper are: funct-an
11
The categories of this paper are: hep-lat
36
The categories of this paper are: cmp-lg
31
The categories of this paper are: ao-sci
37
The categories of this paper are: supr-con
27
The categories of this paper are: comp-gas
8
The categories of this paper are: hep-ex
21
The categories of this paper are: adap-org
15
The categories of this paper are: nucl-ex
13
The categories of this paper are: quant-ph
34
The categories of this paper are: chem-ph
14
The categories of this paper are: math-ph
22
The categories of this paper are: chao-dyn
16
The categories of this paper are: stat
12
The categories of this paper are: nucl-th