Real stable polynomials and matroids: optimization and counting

Several 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 oracle access to an m -variate real polynomial g and to a family of (multi-)subsets ℬ of [ m ], (1) compute the sum of coefficients of monomials in g corresponding to all the sets that appear in B (1), or find S ε ℬ such that the monomial in g corresponding to S has the largest coefficient in g . Special cases of these problems, such as computing permanents and mixed discriminants, sampling from determinantal point processes, and maximizing sub-determinants with combinatorial constraints have been topics of much recent interest in theoretical computer science.

Authors

• Damian Straszak
• Nisheeth K. Vishnoi

Keywords

No keywords are indexed for this paper.