Hyperbolic polynomials approach to Van der Waerden/Schrijver-Valiant like conjectures
From MaRDI portal
Publication:2931405
DOI10.1145/1132516.1132578zbMath1301.90071arXivmath/0510452OpenAlexW2003979730MaRDI QIDQ2931405
Publication date: 25 November 2014
Published in: Proceedings of the thirty-eighth annual ACM symposium on Theory of Computing (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/math/0510452
Analysis of algorithms and problem complexity (68Q25) Convex programming (90C25) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Stochastic matrices (15B51)
Related Items
Counting matchings via capacity-preserving operators, Alternating minimization, scaling algorithms, and the null-cone problem from invariant theory, Linear slices of hyperbolic polynomials and positivity of symmetric polynomial functions, A deterministic approximation algorithm for computing the permanent of a 0, 1 matrix, Randomly colouring graphs (a combinatorial view), Applications of stable polynomials to mixed determinants: Johnson's conjectures, unimodality, and symmetrized Fischer products, Lower Bounds for Partial Matchings in Regular Bipartite Graphs and Applications to the Monomer–Dimer Entropy, An upper bound for permanents of nonnegative matrices, A generalization of permanent inequalities and applications in counting and optimization, A logician's view of graph polynomials, Boolean matrices with prescribed row/column sums and stable homogeneous polynomials: combinatorial and algorithmic applications, Negative dependence and the geometry of polynomials, A polynomial-time algorithm to approximate the mixed volume within a simply exponential factor, Subdeterminant Maximization via Nonconvex Relaxations and Anti-Concentration, Semantic Equivalence of Graph Polynomials Definable in Second Order Logic, Log-concave polynomials. I: Entropy and a deterministic approximation algorithm for counting bases of matroids, Operator scaling: theory and applications, Nash Social Welfare, Matrix Permanent, and Stable Polynomials, Gårding's Theory of Hyperbolic Polynomials, Spectral Analysis of Matrix Scaling and Operator Scaling
