A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries

DOI10.1145/1008731.1008738zbMath1204.65044OpenAlexW2161611531WikidataQ55893500 ScholiaQ55893500MaRDI QIDQ3069905

Eric Vigoda, Alistair Sinclair, Mark R. Jerrum

Publication date: 1 February 2011

Published in: Journal of the ACM (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/1008731.1008738

Mathematics Subject Classification ID

Determinants, permanents, traces, other special matrix functions (15A15) Numerical computation of determinants (65F40) Approximation algorithms (68W25)

Related Items

Majorization and the time complexity of linear optical networks, Sampling Edge Covers in 3-Regular Graphs, Random Instances of Problems in NP – Algorithms and Statistical Physics, Unnamed Item, Model Counting of Monotone Conjunctive Normal Form Formulas with Spectra, Singular values of Gaussian matrices and permanent estimators, Fixed Precision MCMC Estimation by Median of Products of Averages, On the Diaconis-Gangolli Markov Chain for Sampling Contingency Tables with Cell-Bounded Entries, On the Complexity of Constrained Determinantal Point Processes, Approximately Counting and Sampling Small Witnesses Using a Colorful Decision Oracle, Deterministic Random Walks for Rapidly Mixing Chains, Phase Transitions for the Uniform Distribution in the Pattern Maximum Likelihood Problem and its Bethe Approximation, Counting vertices of integral polytopes defined by facets, Smoothed counting of 0–1 points in polyhedra, The Swendsen–Wang dynamics on trees, Inapproximability of positive semidefinite permanents and quantum state tomography, Sequential importance sampling for estimating expectations over the space of perfect matchings, Approximately counting and sampling knowledge states, Perfectly packing graphs with bounded degeneracy and many leaves, Angle-Restricted Sets and Zero-Free Regions for the Permanent, Expander graphs and their applications, Geometric bounds on the fastest mixing Markov chain, Interactions of computational complexity theory and mathematics, Picturing Counting Reductions with the ZH-Calculus, Unnamed Item, Unnamed Item, Unnamed Item, On the Complexity of Holant Problems, Sequential Importance Sampling for Estimating the Number of Perfect Matchings in Bipartite Graphs: An Ongoing Conversation with Laci, Pseudo-Derandomizing Learning and Approximation, Approximating permanents and hafnians, Characterizing optimal sampling of binary contingency tables via the configuration model, ASYMPTOTIC EVALUATION OF BOSONIC PROBABILITY AMPLITUDES IN LINEAR UNITARY NETWORKS IN THE CASE OF LARGE NUMBER OF BOSONS, Monomer-dimer problem on random planar honeycomb lattice, Counting independent sets in graphs with bounded bipartite pathwidth, Unnamed Item, Counting without sampling: Asymptotics of the log-partition function for certain statistical physics models, Enumerating Contingency Tables via Random Permanents, Gibbs rapidly samples colorings of \(G(n, d/n)\), Graph classes and the switch Markov chain for matchings, Stability and complexity of mixed discriminants, Majorization and the number of bipartite graphs for given vertex degrees, Non-commutative circuits and the sum-of-squares problem, Approximately Counting Embeddings into Random Graphs, The Markov chain Monte Carlo revolution, An asymptotic approximation for the permanent of a doubly stochastic matrix, Quantum Chebyshev's Inequality and Applications, Counting Perfect Matchings and the Switch Chain, Counting Hypergraph Colorings in the Local Lemma Regime, On the classical complexity of sampling from quantum interference of indistinguishable bosons, Approximate Counting via Correlation Decay in Spin Systems, Nash Social Welfare, Matrix Permanent, and Stable Polynomials, The number of matchings in random graphs, Fast Computation by Block Permanents of Cumulative Distribution Functions of Order Statistics from Several Populations, Counting Weighted Independent Sets beyond the Permanent, The permanental process, Matrix permanent and quantum entanglement of permutation invariant states, An algorithmic proof of Brégman–Minc theorem, A Decomposition Based Proof for Fast Mixing of a Markov Chain over Balanced Realizations of a Joint Degree Matrix, Towards quantum supremacy with lossy scattershot boson sampling, Dynamic Sampling from Graphical Models, Unnamed Item, A Tight Analysis of Bethe Approximation for Permanent, Randomized sequential importance sampling for estimating the number of perfect matchings in bipartite graphs, Randomly coloring simple hypergraphs with fewer colors, Graph realizations constrained by skeleton graphs, Computing the permanent of (some) complex matrices, Multi-boson correlation sampling, Maximizing products of linear forms, and the permanent of positive semidefinite matrices, Sequential Monte Carlo for counting vertex covers in general graphs, QUANTUM WALKS ON NECKLACES AND MIXING, Computing the permanent modulo a prime power, Are We There Yet? When to Stop a Markov Chain while Generating Random Graphs, Monte Carlo algorithms for computing \(\alpha \)-permanents, Employing the MCMC technique to compute the projection depth in high dimensions, Zero-freeness and approximation of real Boolean Holant problems, Block interpolation: a framework for tight exponential-time counting complexity, Hafnians, perfect matchings and Gaussian matrices, Bandit online optimization over the permutahedron, Simulated tempering and swapping on mean-field models, One-dimensional three-state quantum walk with single-point phase defects, Combinatorics of TCP reordering, Coupling with the stationary distribution and improved sampling for colorings and independent sets, On combinatorial testing problems, Sampling weighted perfect matchings on the square-octagon lattice, On approximating the eigenvalues of stochastic matrices in probabilistic logspace, On the connection between interval size functions and path counting, Exact sampling algorithms for Latin squares and Sudoku matrices via probabilistic divide-and-conquer, On Sampling Simple Paths in Planar Graphs According to Their Lengths, The complexity of generalized domino tilings, Sublinear-time algorithms for monomer-dimer systems on bounded degree graphs, Partial distinguishability as a coherence resource in boson sampling, Stochastic approximation Monte Carlo importance sampling for approximating exact conditional probabilities, The expected characteristic and permanental polynomials of the random Gram matrix, An improved fully polynomial randomized approximation scheme (FPRAS) for counting the number of Hamiltonian cycles in dense digraphs, Hitting time of quantum walks with perturbation, Exponential lower bounds on the complexity of a class of dynamic programs for combinatorial optimization problems, Boson sampling with non-identical single photons, Randomly coloring simple hypergraphs, Approximating multilinear monomial coefficients and maximum multilinear monomials in multivariate polynomials, Negative examples for sequential importance sampling of binary contingency tables, An efficient tree decomposition method for permanents and mixed discriminants, Complexity theory. Abstracts from the workshop held November 14--20, 2021 (hybrid meeting), How many needles are in a haystack, or how to solve \#P-complete counting problems fast, Understanding science through the computational lens, The switch Markov chain for sampling irregular graphs and digraphs, On the construction of graphs with a planar bipartite double cover from Boolean formulas and its application to counting satisfying solutions, Quantum circuits and low-degree polynomials over ${{\mathbb{F}}_\mathsf{2}}$, Some algebraic identities for the \({\alpha}\)-permanent, Some Problems on Approximate Counting in Graphs and Matroids, Combinatorial bandits, Lower bounds for contingency tables via Lorentzian polynomials, Complexity and approximability of the cover polynomial, Permanental partition models and Markovian Gibbs structures, A deterministic approximation algorithm for computing the permanent of a 0, 1 matrix, On testing Hamiltonicity of graphs, On the algebraic complexity of some families of coloured Tutte polynomials, A remark on approximating permanents of positive definite matrices, Modified log-Sobolev inequalities for strongly log-concave distributions, Rank-maximal matchings -- structure and algorithms, An upper bound on the number of high-dimensional permutations, Sampling hypergraphs with given degrees, A faster FPTAS for counting two-rowed contingency tables, The mixing time of switch Markov chains: a unified approach, Coloring invariants of knots and links are often intractable, Matchings in vertex-transitive bipartite graphs, The worm process for the Ising model is rapidly mixing, Relative entropy optimization and its applications, Approximately counting paths and cycles in a graph, Stochastic enumeration method for counting trees, A relationship between subpermanents and the arithmetic-geometric mean inequality, On the number of matrices and a random matrix with prescribed row and column sums and 0-1 entries, Random bichromatic matchings, How should we solve search problems privately?, Permanental generating functions and sequential importance sampling, Hamiltonian cycles in Dirac graphs, Rapid mixing of Gibbs sampling on graphs that are sparse on average, An approximation algorithm for counting contingency tables, Uniform Sampling of Digraphs with a Fixed Degree Sequence, Characterizing limits and opportunities in speeding up Markov chain mixing, Random weighting, asymptotic counting, and inverse isoperimetry, Exact probabilities for the indeterminacy of complex networks as perceived through press perturbations, Boolean matrices with prescribed row/column sums and stable homogeneous polynomials: combinatorial and algorithmic applications, Mixing Times of Markov Chains of 2-Orientations, Sampling and Counting 3-Orientations of Planar Triangulations, Counting and sampling SCJ small parsimony solutions, The Computational Complexity of Estimating MCMC Convergence Time, Bravely, Moderately: A Common Theme in Four Recent Works, Log-concave polynomials. I: Entropy and a deterministic approximation algorithm for counting bases of matroids, Spanning tree constrained determinantal point processes are hard to (approximately) evaluate, Sampling Eulerian orientations of triangular lattice graphs, Scaling matrices and counting the perfect matchings in graphs, A Combinatorial Metrical Task System Problem Under the Uniform Metric, Computing permanents of complex diagonally dominant matrices and tensors, Computing the Partition Function for Perfect Matchings in a Hypergraph, Rapid Mixing and Markov Bases, Counting edge-injective homomorphisms and matchings on restricted graph classes, New permanent approximation inequalities via identities, Approximate counting of standard set-valued tableaux, Randomly coloring constant degree graphs, A load balancing strategy for parallel computation of sparse permanents, Noncommutativity makes determinants hard, On the de-randomization of space-bounded approximate counting problems