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)
- 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
- Binary determinantal complexity
- Towards a dichotomy theorem for the counting constraint satisfaction problem
- The complexity of optimization problems
- Computing small partial coverings
- Random generation of combinatorial structures from a uniform distribution
- A permanent formula with many zero-valued terms
- Counting Small Induced Subgraphs Satisfying Monotone Properties
- Nondeterministic \(NC^1\) computation
- New complexity results about Nash equilibria
- Sampling of bosonic qubits
- Multi-boson correlation sampling
- Non-deterministic exponential time has two-prover interactive protocols
- Approximating the number of monomer-dimer coverings of a lattice.
- Complexity versus stability for classes of propositional formulas
- On the succinct representation of graphs
- On \(\text{TC}^0,\text{AC}^0\), and arithmetic circuits
- Complexity of counting the optimal solutions
- Counting linear extensions
- Faster combinatorial algorithms for determinant and Pfaffian
- Stochastic enumeration method for counting NP-hard problems
- On the counting complexity of propositional circumscription
- Inequalities and identities for generalized matrix functions
- On the generation of circuits and minimal forbidden sets
- Exponentially many perfect matchings in cubic graphs
- Approximate counting, uniform generation and rapidly mixing Markov chains
- On two extremal matrix problems
- Polynomial-time 1-Turing reductions from \(\#\)PH to \(\#\)P
- Holographic algorithms with matchgates capture precisely tractable planar \#CSP
- On the number of Eulerian orientations of a graph
- Holographic algorithms by Fibonacci gates
- On the characterizing properties of the permanental polynomials of graphs
- Small space analogues of Valiant's classes and the limitations of skew formulas
- Counting perfect matchings as fast as Ryser
- Matching theory -- a sampler: From Dénes König to the present
- The complexity of counting self-avoiding walks in subgraphs of two-dimensional grids and hypercubes.
- The ubiquitous Ewens sampling formula
- Dimers on graphs in non-orientable surfaces
- Sparse complete sets for NP: solution of a conjecture of Berman and Hartmanis
- An analysis of Monte Carlo algorithms for counting problems
- The complexity of combinatorial problems with succinct input representation
- Singular values, doubly stochastic matrices, and applications
- On the complexity of inconsistency measurement
- NP is as easy as detecting unique solutions
- Interlacing families. I: Bipartite Ramanujan graphs of all degrees
- Parallel computation with threshold functions
- An extended tree-width notion for directed graphs related to the computation of permanents
- Algorithms for propositional model counting
- An extended tree-width notion for directed graphs related to the computation of permanents
- Counting models for 2SAT and 3SAT formulae
- Scaling matrices and counting the perfect matchings in graphs
- Computing the partition function for perfect matchings in a hypergraph
- On the computational complexity of reconstructing lattice sets from their \(X\)-rays
- Symmetries of plane partitions and the permanent-determinant method
- A deterministic approximation algorithm for computing the permanent of a 0, 1 matrix
- On the complexity of probabilistic abstract argumentation frameworks
- A mildly exponential approximation algorithm for the permanent
- Algebraic independence in positive characteristic: a \(p\)-adic calculus
- Tropical bounds for eigenvalues of matrices
- Weighted enumeration of spanning subgraphs in locally tree-like graphs
- Approximately counting embeddings into random graphs
- Per-spectral characterizations of some edge-deleted subgraphs of a complete graph
- Boolean circuits versus arithmetic circuits
- Bayesian incentive compatibility via matchings
- Computing expectations and marginal likelihoods for permutations
- Subtractive reductions and complete problems for counting complexity classes
- On the hardness of approximate reasoning
- A fast parametric assignment algorithm with applications in max-algebra
- Federation and navigation in SPARQL 1.1
- Boson sampling with non-identical single photons
- On the computational complexity of the Jones and Tutte polynomials
- Approximate profile maximum likelihood
- Parameterized counting problems
- Permanental bounds for the signless Laplacian matrix of a unicyclic graph with diameter \(d\)
- Hard Enumeration Problems in Geometry and Combinatorics
- Algorithms to count paths and cycles
- Asymptotic evaluation of bosonic probability amplitudes in linear unitary networks in the case of large number of bosons
- Complexity of fundamental problems in probabilistic abstract argumentation: beyond independence
- On the coefficients of the permanent and the determinant of a circulant matrix: applications
- Lee-Yang theorems and the complexity of computing averages
- A note on the permanental roots of bipartite graphs
- Brace generation
- Permanental bounds for the signless Laplacian matrix of bipartite graphs and unicyclic graphs
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)
