Enumerating Contingency Tables via Random Permanents

DOI10.1017/S0963548307008668zbMath1132.62045arXivmath/0511596MaRDI QIDQ5448988

Alexander I. Barvinok

Publication date: 10 March 2008

Published in: Combinatorics, Probability and Computing (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Exact enumeration problems, generating functions (05A15) Determinants, permanents, traces, other special matrix functions (15A15) Random matrices (algebraic aspects) (15B52) Contingency tables (62H17)

Related Items

Brunn--Minkowski inequalities for contingency tables and integer flows, On the mixing time of the Diaconis-Gangolli random walk on contingency tables over \(\mathbb{Z}/q\mathbb{Z} \), An approximation algorithm for counting contingency tables, Majorization and the number of bipartite graphs for given vertex degrees, Random sampling of contingency tables via probabilistic divide-and-conquer

Cites Work

• The Van der Waerden conjecture for mixed discriminants
• The solution of van der Waerden's problem for permanents
• Log-Sobolev inequalities and sampling from log-concave distributions
• A deterministic algorithm for approximating the mixed discriminant and mixed volume, and a combinatorial corollary
• Counting integer flows in networks
• Algebraic algorithms for sampling from conditional distributions
• On the complexity of nonnegative-matrix scaling
• On complexity of matrix scaling
• On matrices with doubly stochastic pattern
• A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries
• Approximately counting integral flows and cell-bounded contingency tables
• New permanental upper bounds for nonnegative matrices
• Improved bounds for sampling contingency tables
• A polynomial-time algorithm to approximately count contingency tables when the number of rows is constant
• A deterministic strongly polynomial algorithm for matrix scaling and approximate permanents