The complexity of computing the permanent
From MaRDI portal
Cites work
- scientific article; zbMATH DE number 3141365 (Why is no real title available?)
- scientific article; zbMATH DE number 3182201 (Why is no real title available?)
- scientific article; zbMATH DE number 3557236 (Why is no real title available?)
- scientific article; zbMATH DE number 3569828 (Why is no real title available?)
- scientific article; zbMATH DE number 3571502 (Why is no real title available?)
- scientific article; zbMATH DE number 3419161 (Why is no real title available?)
- A characterization of convertible (0,1)-matrices
- A lower bound on the number of additions in monotone computations
- A method for obtaining digital signatures and public-key cryptosystems
- An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
- An Algorithm for Distinct Representatives
- Every Prime Has a Succinct Certificate
- Gaussian elimination is not optimal
- On the computational power of pushdown automata
- On the relation between the determinant and the permanent
- Relative complexity of checking and evaluating
- The Complexity of Enumeration and Reliability Problems
- The complexity of theorem-proving procedures
- The polynomial-time hierarchy
Cited in
(only showing first 100 items - show all)- The Power of Self-Reducibility: Selectivity, Information, and Approximation
- Comparison of permanental bounds of \((0,1)\)-matrices
- Computation of Exact Bootstrap Confidence Intervals: Complexity and Deterministic Algorithms
- Enumerative counting is hard
- \texttt{QOptCraft}: a python package for the design and study of linear optical quantum systems
- Monomials, multilinearity and identity testing in simple read-restricted circuits
- Resolving contradictions: A plausible semantics for inconsistent systems
- The Thompson-Higman monoids \(M_{k,i}\): the \(\mathcal J\)-order, the \(\mathcal D\)-relation, and their complexity.
- Turing machines with few accepting computations and low sets for PP
- Fast computation of discrete invariants associated to a differential rational mapping
- Algorithms and complexity for Turaev-Viro invariants
- A relationship between subpermanents and the arithmetic-geometric mean inequality
- On the complexity of computing Kostka numbers and Littlewood-Richardson coefficients
- New permanent approximation inequalities via identities
- Algorithms and complexity for Turaev-Viro invariants
- Bernoulli measure on strings, and Thompson-Higman monoids.
- An improved fully polynomial randomized approximation scheme (FPRAS) for counting the number of Hamiltonian cycles in dense digraphs
- An oracle builder's toolkit
- Relativized counting classes: Relations among thresholds, parity, and mods
- Almost all trees are co-immanantal
- Counting induced subgraphs: a topological approach to \#W[1]-hardness
- The complexity of the characteristic and the minimal polynomial.
- On characteristic and permanent polynomials of a matrix
- New upper bound for the \#3-SAT problem
- On the complexity of counting in the polynomial hierarchy
- Permanents of woven matrices
- A duality between Boolean functions
- A theory of even functionals and their algorithmic applications
- Independent sets versus perfect matchings
- Approximation algorithm for DNF under distributions with limited independence
- A loop-free algorithm for generating the linear extensions of a poset
- Counting and sampling SCJ small parsimony solutions
- The combinatorics of N. G. de Bruijn
- Regular expression order-sorted unification and matching
- The computational complexity of evolutionarily stable strategies
- Probabilistic polynomials, AC\(^ 0\) functions and the polynomial-time hierarchy
- Consecutive ones property and PQ-trees for multisets: hardness of counting their orderings
- The permanental process
- Per-spectral characterizations of bicyclic networks
- Similarity of personal preferences: Theoretical foundations and empirical analysis
- A note on enumerative counting
- A hybrid algorithm for computing permanents of sparse matrices
- On the power of parity polynomial time
- Nilpotent quantum mechanics
- A permanent formula for the Jones polynomial
- Shortest \((A+B)\)-path packing via hafnian
- Immanants and finite point processes
- The complexity of computing the random priority allocation matrix
- The factorization of the permanent of a matrix with minimal rank in prime characteristic
- On the complexity of immanants
- Counting Hamiltonian cycles on quartic 4-vertex-connected planar graphs
- Sequential importance sampling for estimating expectations over the space of perfect matchings
- Counting integral points in polytopes via numerical analysis of contour integration
- The Second Immanantal Polynomial and the Centroid of a Graph
- Calculation of the permanent of a sparse positive matrix
- A partially structure-preserving algorithm for the permanents of adjacency matrices of fullerenes
- One complexity theorist's view of quantum computing
- On Listing, Sampling, and Counting the Chordal Graphs with Edge Constraints
- Counting restricted homomorphisms via Möbius inversion over matroid lattices
- Fast computation by block permanents of cumulative distribution functions of order statistics from several populations
- Cook's versus Valiant's hypothesis
- Rectangular Kronecker coefficients and plethysms in geometric complexity theory
- New permanental bounds for Ferrers matrices
- Per-spectral characterizations of some bipartite graphs
- Lower bounds for the determinantal complexity of explicit low degree polynomials
- PSPACE is provable by two provers in one round
- Coloring invariants of knots and links are often intractable
- Descriptional and computational complexity of finite automata -- a survey
- On the fixed parameter complexity of graph enumeration problems definable in monadic second-order logic
- Random path method with pivoting for computing permanents of matrices
- Hard Enumeration Problems in Geometry and Combinatorics
- Concentration of permanent estimators for certain large matrices.
- On the depth complexity of formulas
- The complexity of computing the number of strings of given length in context-free languages
- Commuting quantum circuits and complexity of Ising partition functions
- Classification of a Class of Counting Problems Using Holographic Reductions
- On the complexity of convex hulls of subsets of the two-dimensional plane
- Approximate inclusion-exclusion
- Computing the permanent modulo a prime power
- On testing monomials in multivariate polynomials
- On the algebraic complexity of some families of coloured Tutte polynomials
- Graph factors and factorization: 1985--2003: a survey
- A lower bound for monotone arithmetic circuits computing \(0-1\) permanent
- Arithmetization: A new method in structural complexity theory
- Geometric complexity theory. III: On deciding nonvanishing of a Littlewood-Richardson coefficient
- Graph isomorphism problem
- A very hard log-space counting class
- DNF sparsification and a faster deterministic counting algorithm
- Counting and enumeration complexity with application to multicriteria scheduling
- A relation-algebraic approach to simple games
- Simple characterizations of \(P(\# P)\) and complete problems
- Solving PP-Complete and #P-Complete Problems by P Systems with Active Membranes
- Graph Isomorphism is in SPP
- The complexity of power-index comparison
- Partition functions on \(k\)-regular graphs with \(\{0,1\}\)-vertex assignments and real edge functions
- Approximating the permanent: A simple approach
- Exact algorithms for exact satisfiability and number of perfect matchings
- The expected characteristic and permanental polynomials of the random Gram matrix
- A \(q\)-analog of approximation inclusion-exclusion
- Holographic reduction, interpolation and hardness
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)
