The complexity of computing the permanent
From MaRDI portal
Publication:600247
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)- 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
- Pfaffian orientations and perfect matchings of scale-free networks
- Permanent and determinant
- Solving \#SAT using vertex covers
- On counting problems and the polynomial-time hierarchy
- Efficiently computing the permanent and Hafnian of some banded Toeplitz matrices
- Pfaffian orientations, 0-1 permanents, and even cycles in directed graphs
- Permanent versus determinant over a finite field
- Approximating the least hypervolume contributor: NP-hard in general, but fast in practice
- Graphs determined by polynomial invariants
- Games against nature
- Enumerating perfect matchings in \(n\)-cubes
- Pfaffian graphs embedding on the torus
- On the Pólya permanent problem over finite fields
- A note on the determinant and permanent problem
- Classifying the computational complexity of problems
- On enumerating monomials and other combinatorial structures by polynomial interpolation
- A dichotomy in the complexity of counting database repairs
- Relationships among $PL$, $\#L$, and the determinant
- Counting without sampling: Asymptotics of the log-partition function for certain statistical physics models
- Extremal graphs with a given number of perfect matchings
- Structure and importance of logspace-MOD class
- On the expected number of perfect matchings in cubic planar graphs
- Feasible arithmetic computations: Valiant's hypothesis
- Computing functions with parallel queries to NP
- Algorithmic uses of the Feferman-Vaught theorem
- Holant problems for 3-regular graphs with complex edge functions
- Leveraging Belief Propagation, Backtrack Search, and Statistics for Model Counting
- Hafnians, perfect matchings and Gaussian matrices
- On the hardness of computing the permanent of random matrices
- On the Expressive Power of Planar Perfect Matching and Permanents of Bounded Treewidth Matrices
- The complexity of approximating bounded-degree Boolean \(\#\)CSP
- On unique graph 3-colorability and parsimonious reductions in the plane
- The number of matchings in random graphs
- Bandit online optimization over the permutahedron
- Extending matchings in graphs: A survey
- Singular values of Gaussian matrices and permanent estimators
- A Tighter Bound for Counting Max-Weight Solutions to 2SAT Instances
- Model counting for CNF formulas of bounded modular treewidth
- Approximating the permanent of graphs with large factors
- NP-completeness of some problems concerning voting games
- On deterministic approximation of DNF
- The combinatorial approach yields an NC algorithm for computing Pfaffians
- Generalized theorems on relationships among reducibility notions to certain complexity classes
- A complexity theory of constructible functions and sheaves
- The structure and complexity of Nash equilibria for a selfish routing game
- On the frontiers of polynomial computations in tropical geometry
- Oriented Euler complexes and signed perfect matchings
- Efficient importance sampling for binary contingency tables
- On the permanent of certain \((0,1)\) Toeplitz matrices
- Solution Counting Algorithms for Constraint-Centered Search Heuristics
- On the permanental polynomials of matrices
- On the parameterized complexity of approximate counting
- NC algorithms for computing the number of perfect matchings in \(K_{3,3}\)-free graphs and related problems
- Counting problems over the reals
- Locating \(P\)/poly optimally in the extended low hierarchy
- On the coefficients of the permanent and the determinant of a circulant matrix: applications
- An asymptotic approximation for the permanent of a doubly stochastic matrix
- Parameterized counting problems
- On the closure of certain function classes under integer division by polynomially-bounded functions
- On testing Hamiltonicity of graphs
- Counting minimal transversals of \(\beta\)-acyclic hypergraphs
- Singular spaces of matrices and their application in combinatorics
- Counting problems and ranks of matrices
- Cycle-maximal triangle-free graphs
- Leveraging belief propagation, backtrack search, and statistics for model counting
- Counting maximal independent sets in directed path graphs
- On some natural complete operators
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)
