Real stable polynomials and matroids: optimization and counting

DOI10.1145/3055399.3055457MaRDI QIDQ4977986zbMATH OpenOpenAlexFDO

Authors Damian Straszak, Nisheeth K. Vishnoi

Publication date 17 August 2017

Published in Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1611.04548

zbMATH Keywords

approximation algorithmsconvex optimizationentropymatroidsreal stable polynomials

Mathematics Subject Classification ID

Approximation algorithms (68W25) Convex programming (90C25) Combinatorial optimization (90C27) Approximation methods and heuristics in mathematical programming (90C59)

Abstract: 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 $SinB$ 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.

Recommendations

• A generalization of permanent inequalities and applications in counting and optimization
• A generalization of permanent inequalities and applications in counting and optimization
• Log-concave polynomials. I: Entropy and a deterministic approximation algorithm for counting bases of matroids
• Hyperbolic polynomials, interlacers, and sums of squares
• Convex Matroid Optimization

Cited in

(23)

• The Ising partition function: zeros and deterministic approximation
• Conic stability of polynomials and positive maps
• Log-concave polynomials. I: Entropy and a deterministic approximation algorithm for counting bases of matroids
• Maximizing products of linear forms, and the permanent of positive semidefinite matrices
• Paving property for real stable polynomials and strongly Rayleigh processes
• Convergence of the non-uniform physarum dynamics
• Conic stability of polynomials
• Imaginary projections: complex versus real coefficients
• Combinatorial Bernoulli factories
• Subdeterminant maximization via nonconvex relaxations and anti-concentration
• A generalization of permanent inequalities and applications in counting and optimization
• On the complexity of constrained determinantal point processes
• Proportional volume sampling and approximation algorithms for \(A\)-optimal design
• Fisher Zeros and Correlation Decay in the Ising Model
• Fisher zeros and correlation decay in the Ising model
• Maximizing determinants under partition constraints
• Dynamic Sampling from Graphical Models
• Counting matchings via capacity-preserving operators
• Combinatorics and preservation of conically stable polynomials
• scientific article; zbMATH DE number 7758358 (Why is no real title available?)
• The sparseness of g-convex functions
• Capacity bounds on integral flows and the Kostant partition function
• From trees to polynomials and back again: new capacity bounds with applications to TSP

This page was built for publication: Real stable polynomials and matroids: optimization and counting

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4977986)