The complexity of computing the permanent
From MaRDI portal
Publication:600247
DOI10.1016/0304-3975(79)90044-6zbMATH Open0415.68008DBLPjournals/tcs/Valiant79OpenAlexW2006912660WikidataQ55885263 ScholiaQ55885263MaRDI QIDQ600247FDOQ600247
Authors: Leslie G. Valiant 
Publication date: 1979
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0304-3975(79)90044-6
Analysis of algorithms and problem complexity (68Q25) Determinants, permanents, traces, other special matrix functions (15A15)
Cites Work
- Title not available (Why is that?)
- A characterization of convertible (0,1)-matrices
- A method for obtaining digital signatures and public-key cryptosystems
- Gaussian elimination is not optimal
- Title not available (Why is that?)
- Title not available (Why is that?)
- The Complexity of Enumeration and Reliability Problems
- The complexity of theorem-proving procedures
- Title not available (Why is that?)
- An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
- On the computational power of pushdown automata
- A lower bound on the number of additions in monotone computations
- The polynomial-time hierarchy
- Relative complexity of checking and evaluating
- On the relation between the determinant and the permanent
- Title not available (Why is that?)
- An Algorithm for Distinct Representatives
- Every Prime Has a Succinct Certificate
- Title not available (Why is that?)
Cited In (only showing first 100 items - show all)
- On testing monomials in multivariate polynomials
- Solving PP-Complete and #P-Complete Problems by P Systems with Active Membranes
- On deterministic approximation of DNF
- A complexity theory of constructible functions and sheaves
- Permanent and determinant
- On the frontiers of polynomial computations in tropical geometry
- Hard Enumeration Problems in Geometry and Combinatorics
- Arithmetization: A new method in structural complexity theory
- On unique graph 3-colorability and parsimonious reductions in the plane
- The structure and complexity of Nash equilibria for a selfish routing game
- The expected characteristic and permanental polynomials of the random Gram matrix
- On the Pólya permanent problem over finite fields
- Feasible arithmetic computations: Valiant's hypothesis
- Singular values of Gaussian matrices and permanent estimators
- A very hard log-space counting class
- Graphs determined by polynomial invariants
- A note on the determinant and permanent problem
- Counting without sampling: Asymptotics of the log-partition function for certain statistical physics models
- Structure and importance of logspace-MOD class
- Algorithmic uses of the Feferman-Vaught theorem
- Exact algorithms for exact satisfiability and number of perfect matchings
- A \(q\)-analog of approximation inclusion-exclusion
- On the depth complexity of formulas
- Approximating the permanent of graphs with large factors
- On the permanent of certain \((0,1)\) Toeplitz matrices
- On the complexity of convex hulls of subsets of the two-dimensional plane
- NP-completeness of some problems concerning voting games
- Geometric complexity theory. III: On deciding nonvanishing of a Littlewood-Richardson coefficient
- The complexity of power-index comparison
- Efficiently computing the permanent and Hafnian of some banded Toeplitz matrices
- Generalized theorems on relationships among reducibility notions to certain complexity classes
- Computing functions with parallel queries to NP
- Solving \#SAT using vertex covers
- Games against nature
- Holant problems for 3-regular graphs with complex edge functions
- Hafnians, perfect matchings and Gaussian matrices
- Classification of a Class of Counting Problems Using Holographic Reductions
- Partition functions on \(k\)-regular graphs with \(\{0,1\}\)-vertex assignments and real edge functions
- Approximating the least hypervolume contributor: NP-hard in general, but fast in practice
- Extremal graphs with a given number of perfect matchings
- On the expected number of perfect matchings in cubic planar graphs
- Simple characterizations of \(P(\# P)\) and complete problems
- Approximating the permanent: A simple approach
- Bandit online optimization over the permutahedron
- On counting problems and the polynomial-time hierarchy
- The combinatorial approach yields an NC algorithm for computing Pfaffians
- Oriented Euler complexes and signed perfect matchings
- Computing the permanent modulo a prime power
- Model counting for CNF formulas of bounded modular treewidth
- On the algebraic complexity of some families of coloured Tutte polynomials
- Relationships among $PL$, $\#L$, and the determinant
- On the hardness of computing the permanent of random matrices
- On the fixed parameter complexity of graph enumeration problems definable in monadic second-order logic
- A lower bound for monotone arithmetic circuits computing \(0-1\) permanent
- DNF sparsification and a faster deterministic counting algorithm
- A Tighter Bound for Counting Max-Weight Solutions to 2SAT Instances
- Commuting quantum circuits and complexity of Ising partition functions
- Efficient importance sampling for binary contingency tables
- Descriptional and computational complexity of finite automata -- a survey
- Classifying the computational complexity of problems
- Concentration of permanent estimators for certain large matrices.
- Holographic reduction, interpolation and hardness
- Graph factors and factorization: 1985--2003: a survey
- Pfaffian orientations, 0-1 permanents, and even cycles in directed graphs
- The number of matchings in random graphs
- Extending matchings in graphs: A survey
- Approximate inclusion-exclusion
- Pfaffian orientations and perfect matchings of scale-free networks
- Permanent versus determinant over a finite field
- Enumerating perfect matchings in \(n\)-cubes
- Pfaffian graphs embedding on the torus
- Leveraging Belief Propagation, Backtrack Search, and Statistics for Model Counting
- Graph isomorphism problem
- Random path method with pivoting for computing permanents of matrices
- The complexity of computing the number of strings of given length in context-free languages
- A relation-algebraic approach to simple games
- Graph Isomorphism is in SPP
- On enumerating monomials and other combinatorial structures by polynomial interpolation
- A dichotomy in the complexity of counting database repairs
- On the Expressive Power of Planar Perfect Matching and Permanents of Bounded Treewidth Matrices
- Counting and enumeration complexity with application to multicriteria scheduling
- The complexity of approximating bounded-degree Boolean \(\#\)CSP
- Odd \(K_{3,3}\) subdivisions in bipartite graphs
- Approximately counting approximately-shortest paths in directed acyclic graphs
- A dichotomy for real weighted Holant problems
- The complexity of estimating min-entropy
- The time complexity of the token swapping problem and its parallel variants
- Finding all maximally-matchable edges in a bipartite graph
- Computing the permanental polynomials of bipartite graphs by Pfaffian orientation
- Characterizing properties of permanental polynomials of lollipop graphs
- Per-spectral characterizations of graphs with extremal per-nullity
- Approximately counting paths and cycles in a graph
- Masking traveling beams: optical solutions for NP-complete problems, trading space for time
- Tensors in computations
- An upper bound on the number of high-dimensional permutations
- Unification algorithms cannot be combined in polynomial time
- The minimal \(k\)-core problem for modeling \(k\)-assemblies
- On the skew-permanental polynomials of orientation graphs
- The complexity of counting locally maximal satisfying assignments of Boolean CSPs
- Computing the permanent of (some) complex matrices
This page was built for publication: The complexity of computing the permanent
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q600247)
