The complexity of computing the permanent

From MaRDI portal

Publication:600247

Jump to:navigation, search

DOI10.1016/0304-3975(79)90044-6zbMath0415.68008OpenAlexW2006912660WikidataQ55885263 ScholiaQ55885263MaRDI QIDQ600247

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

zbMATH Keywords

computational complexity determinant permanent of a matrix

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Determinants, permanents, traces, other special matrix functions (15A15)

Related Items

Affine projections of symmetric polynomials., Some observations on holographic algorithms, Fast computation of discrete invariants associated to a differential rational mapping, Concentration of permanent estimators for certain large matrices., The fewest clues problem, Graphs determined by polynomial invariants, The complexity to compute the Euler characteristic of complex varieties, The combinatorial approach yields an NC algorithm for computing Pfaffians, The computational complexity of calculating partition functions of optimal medians with Hamming distance, Limit theorems for random permanents with exchangeable structure, Kräuter conjecture on permanents is true, On blockwise symmetric matchgate signatures and higher domain \#CSP, Pisot unit generators in number fields, Singular values, doubly stochastic matrices, and applications, Block interpolation: a framework for tight exponential-time counting complexity, A stability result using the matrix norm to bound the permanent, The number of matrices with nonzero permanent over a finite field, On the complexity of energy storage problems, A loop-free algorithm for generating the linear extensions of a poset, Sampling weighted perfect matchings on the square-octagon lattice, A mildly exponential approximation algorithm for the permanent, On the number of Eulerian orientations of a graph, On deterministic approximation of DNF, Maximum matchings and minimum dominating sets in Apollonian networks and extended tower of Hanoi graphs, Short rational generating functions for solving some families of fuzzy integer programming problems, Permanental bounds for the signless Laplacian matrix of a unicyclic graph with diameter \(d\), Holographic reduction, interpolation and hardness, On characteristic and permanent polynomials of a matrix, Ulrich complexity, Understanding the complexity of axiom pinpointing in lightweight description logics, On the Gibson barrier for the Pólya problem, Approximate counting in SMT and value estimation for probabilistic programs, Holographic algorithms by Fibonacci gates, A sufficient condition for Pfaffian graphs on the torus, The complexity of approximating bounded-degree Boolean \(\#\)CSP, On the characterizing properties of the permanental polynomials of graphs, The probabilistic minimum dominating set problem, Farrell polynomials on graphs of bounded tree width, An oracle builder's toolkit, The complexity of the characteristic and the minimal polynomial., The complexity of counting self-avoiding walks in subgraphs of two-dimensional grids and hypercubes., Approximating multilinear monomial coefficients and maximum multilinear monomials in multivariate polynomials, Small space analogues of Valiant's classes and the limitations of skew formulas, On the construction of graphs with a planar bipartite double cover from Boolean formulas and its application to counting satisfying solutions, Independence number and the number of maximum independent sets in pseudofractal scale-free web and Sierpiński gasket, On the number of different permanents of some sparse (0,1)-circulant matrices., Permanent formulae from the Veronesean, An upper bound for the permanent of \((0,1)\)-matrices., The complexity of Bayesian networks specified by propositional and relational languages, Counting minimal transversals of \(\beta\)-acyclic hypergraphs, Pfaffian polyominos on the Klein bottle, The complexity of problems for quantified constraints, A deterministic approximation algorithm for computing the permanent of a 0, 1 matrix, On the hardness of counting problems of complete mappings., Fine-grained dichotomies for the Tutte plane and Boolean \#CSP, Approximate inference in Bayesian networks: parameterized complexity results, On the algebraic complexity of some families of coloured Tutte polynomials, Computing the permanental polynomials of graphs, Cook's versus Valiant's hypothesis, Complexity classes and completeness in algebraic geometry, Coloring invariants of knots and links are often intractable, An \(O(|E(G)|^2)\) algorithm for recognizing Pfaffian graphs of a type of bipartite graphs, The complexity of counting models of linear-time temporal logic, Sublinear-space and bounded-delay algorithms for maximal clique enumeration in graphs, Constructing graphs which are permanental cospectral and adjacency cospectral, On the (signless) Laplacian permanental polynomials of graphs, Many associated primes of powers of primes, Extremal octagonal chains with respect to the coefficients sum of the permanental polynomial, The complexity of planar Boolean \#CSP with complex weights, Non-deterministic weighted automata evaluated over Markov chains, Unicyclic graphs with second largest and second smallest permanental sums, Counting substrate cycles in topologically restricted metabolic networks, On the generation of circuits and minimal forbidden sets, Counting models for 2SAT and 3SAT formulae, Matrix permanent inequalities for approximating joint assignment matrices in tracking systems, Counting maximal independent sets in directed path graphs, Some results on certain generalized circulant matrices, Computing the optimal partition of variables in multi-homogeneous homotopy methods, On measures of space over real and complex numbers, An efficient algorithm for deciding vanishing of Schubert polynomial coefficients, Converting immanants on skew-symmetric matrices, Approximation theorems for random permanents and associated stochastic processes, Computational complexity and 3-manifolds and zombies, The ubiquitous Ewens sampling formula, The complexity of error metrics, Enumerative counting is hard, Non-cancellative Boolean circuits: A generalization of monotone boolean circuits, On \(\text{TC}^0,\text{AC}^0\), and arithmetic circuits, Counting problems over the reals, Subcomplete generalizations of graph isomorphism, An analysis of Monte Carlo algorithm for estimating the permanent, Strong orientations without even directed circuits, Immanants and finite point processes, Approximating the number of monomer-dimer coverings of a lattice., Tally NP sets and easy census functions., Unification algorithms cannot be combined in polynomial time., Computation of sparse circulant permanents via determinants, Voronoi-like nondeterministic partition of a lattice by collectives of finite automata, Permanents of woven matrices, One complexity theorist's view of quantum computing, Randomized sequential importance sampling for estimating the number of perfect matchings in bipartite graphs, The minimal \(k\)-core problem for modeling \(k\)-assemblies, The complexity of counting locally maximal satisfying assignments of Boolean CSPs, On the skew-permanental polynomials of orientation graphs, Computing the permanent of (some) complex matrices, Binary determinantal complexity, A permanent formula with many zero-valued terms, Counting induced subgraphs: an algebraic approach to \(\#\)W[1-hardness], Multi-boson correlation sampling, Complexity versus stability for classes of propositional formulas, Complexity of counting the optimal solutions, The structure and complexity of Nash equilibria for a selfish routing game, Holant problems for 3-regular graphs with complex edge functions, Hafnians, perfect matchings and Gaussian matrices, Masking traveling beams: optical solutions for NP-complete problems, trading space for time, Faster combinatorial algorithms for determinant and Pfaffian, Bandit online optimization over the permutahedron, Model counting for CNF formulas of bounded modular treewidth, Stochastic enumeration method for counting NP-hard problems, DNF sparsification and a faster deterministic counting algorithm, Graph factors and factorization: 1985--2003: a survey, Random path method with pivoting for computing permanents of matrices, On unique graph 3-colorability and parsimonious reductions in the plane, Algorithms for four variants of the exact satisfiability problem, Average-case intractability vs. worst-case intractability, Algorithmic uses of the Feferman-Vaught theorem, Permanent versus determinant over a finite field, On the Pólya permanent problem over finite fields, Pfaffian graphs embedding on the torus, Enumerating perfect matchings in \(n\)-cubes, Optical solution for hard on average \#P-complete instances (using exponential space for solving instances of the permanent), On enumerating monomials and other combinatorial structures by polynomial interpolation, A dichotomy in the complexity of counting database repairs, Partition functions on \(k\)-regular graphs with \(\{0,1\}\)-vertex assignments and real edge functions, On testing monomials in multivariate polynomials, 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, Matching signatures and Pfaffian graphs, Finding all maximally-matchable edges in a bipartite graph, Approximating the least hypervolume contributor: NP-hard in general, but fast in practice, A relation-algebraic approach to simple games, New permanental bounds for Ferrers matrices, Geometric complexity theory. III: On deciding nonvanishing of a Littlewood-Richardson coefficient, Lower bounds for the determinantal complexity of explicit low degree polynomials, Computing the permanental polynomials of bipartite graphs by Pfaffian orientation, Complexity and approximability of the cover polynomial, The consequences of eliminating NP solutions, On the Pólya conversion problem for permanents and determinants, On testing Hamiltonicity of graphs, Counting problems and ranks of matrices, Cycle-maximal triangle-free graphs, The factorization of the permanent of a matrix with minimal rank in prime characteristic, An upper bound on the number of high-dimensional permutations, Lower bounds against weakly-uniform threshold circuits, Per-spectral characterizations of graphs with extremal per-nullity, Per-spectral characterizations of bicyclic networks, A theory of even functionals and their algorithmic applications, Independent sets versus perfect matchings, Computing functions with parallel queries to NP, Approximation algorithm for DNF under distributions with limited independence, Counting the number of perfect matchings in \(K_{5}\)-free graphs, Mathematical aspects of concept analysis, Relative entropy optimization and its applications, On the permanents of circulant and degenerate Schur matrices, Maximal independent sets in a generalisation of caterpillar graph, Robust planning with incomplete domain models, Approximately counting paths and cycles in a graph, Probabilistic polynomials, AC\(^ 0\) functions and the polynomial-time hierarchy, Arithmetization: A new method in structural complexity theory, Non-deterministic exponential time has two-prover interactive protocols, Finding a shortest non-zero path in group-labeled graphs via permanent computation, Approximate counting for complex-weighted Boolean constraint satisfaction problems, Consecutive ones property and PQ-trees for multisets: hardness of counting their orderings, Maximum matchings in scale-free networks with identical degree distribution, Leveraging belief propagation, backtrack search, and statistics for model counting, Descriptional and computational complexity of finite automata -- a survey, Exponentially many perfect matchings in cubic graphs, Calculation of the permanent of a sparse positive matrix, A partially structure-preserving algorithm for the permanents of adjacency matrices of fullerenes, An efficient algorithm for computing permanental polynomials of graphs, A permanent formula for the Jones polynomial, Shortest \((A+B)\)-path packing via hafnian, The combinatorics of N. G. de Bruijn, Counting and sampling SCJ small parsimony solutions, Regular expression order-sorted unification and matching, On the permanental polynomials of matrices, Almost all trees are co-immanantal, Maximal independent sets in caterpillar graphs, Bernoulli measure on strings, and Thompson-Higman monoids., New permanent approximation inequalities via identities, Computing expectations and marginal likelihoods for permutations, Counting induced subgraphs: a topological approach to \#W[1-hardness], On the succinct representation of graphs, On the complexity of counting in the polynomial hierarchy, A note on enumerative counting, Similarity of personal preferences: Theoretical foundations and empirical analysis, Odd \(K_{3,3}\) subdivisions in bipartite graphs, Approximately counting approximately-shortest paths in directed acyclic graphs, The complexity of estimating min-entropy, A dichotomy for real weighted Holant problems, On the linear classification of even and odd permutation matrices and the complexity of computing the permanent, On the bivariate permanent polynomials of graphs, On preprocessing techniques and their impact on propositional model counting, A lower bound for the determinantal complexity of a hypersurface, Convertible, nearly decomposable, and nearly reducible matrices, A hybrid algorithm for computing permanents of sparse matrices, Maximizing products of linear forms, and the permanent of positive semidefinite matrices, Efficient computation of permanents, with applications to boson sampling and random matrices, Polynomial time algorithm for an optimal stable assignment with multiple partners, Further results on the star degree of graphs, On the hardness of the determinant: sum of regular set-multilinear circuits, Completeness, approximability and exponential time results for counting problems with easy decision version, Reduced word enumeration, complexity, and randomization, New upper bound for the \#3-SAT problem, A hybrid algorithm for multi-homogeneous Bézout number, Counting for satisfiability by inverting resolution, Factorially many maximum matchings close to the Erdős-Gallai bound, Efficient importance sampling for binary contingency tables, The Hafnian master theorem, On the complexity of finding shortest variable disjunction branch-and-bound proofs, Rectangular Kronecker coefficients and plethysms in geometric complexity theory, Per-spectral characterizations of some bipartite graphs, Reliable maximin-maxisum locations for maximum service availability on tree networks vulnerable to disruptions, On approximating the eigenvalues of stochastic matrices in probabilistic logspace, On the connection between interval size functions and path counting, Vanishing symmetric Kronecker coefficients, A general purpose algorithm for counting simple cycles and simple paths of any length, Circulant matrices and Galois-Togliatti systems, Syzygies of the apolar ideals of the determinant and permanent, The Pfaffian property of graphs on the Möbius strip based on topological resolution, \( \pm 1\)-matrices with vanishing permanent, Parameterized complexity of determinant and permanent, Handling and measuring inconsistency in non-monotonic logics, A structured view on weighted counting with relations to counting, quantum computation and applications, Algorithms for orbit closure separation for invariants and semi-invariants of matrices, Descriptive complexity of \#P functions: a new perspective, Counting polygon triangulations is hard, Computing the permanent of the Laplacian matrices of nonbipartite graphs, Mathematical logic: proof theory, constructive mathematics. Abstracts from the workshop held November 8--14, 2020 (hybrid meeting), Computational complexity of flat and generic assumption-based argumentation, with and without probabilities, New width parameters for SAT and \#SAT, Open-world probabilistic databases: semantics, algorithms, complexity, Lee-Yang theorems and the complexity of computing averages, An extended tree-width notion for directed graphs related to the computation of permanents, Arithmetic matrix operations that preserve conversion, Algorithms for propositional model counting, Improved approximations for the Erlang loss model, Solution counting algorithms for constraint-centered search heuristics, Query evaluation on a database given by a random graph, Generalized Kakeya sets for polynomial evaluation and faster computation of fermionants, Some extremal graphs with respect to permanental sum, Permanental sums of graphs of extreme sizes, The robustness of LWPP and WPP, with an application to graph reconstruction, Parameterized counting of partially injective homomorphisms, Tropicalization, symmetric polynomials, and complexity, The expectation value of the number of loops and the left-passage probability in the double-dimer model, Recent progress in combinatorial random matrix theory, Robustness of approval-based multiwinner voting rules, Counting the number of perfect matchings, and generalized decision trees, Permanent, determinant, and rank of bi-block graphs, Lower bounds for arithmetic circuits via the Hankel matrix, The opacity of backbones, The characterizing properties of (signless) Laplacian permanental polynomials of almost complete graphs, Sharp bounds on the permanental sum of a graph, Definability for model counting, Singular tuples of matrices is not a null cone (and the symmetries of algebraic varieties), Counting Hamiltonian cycles on quartic 4-vertex-connected planar graphs, Spanning tree constrained determinantal point processes are hard to (approximately) evaluate, Operator scaling: theory and applications, Pfaffian pairs and parities: counting on linear matroid intersection and parity problems, Generalized permanental polynomials of graphs, Vanishing of Littlewood-Richardson polynomials is in P, On the permanent of a random symmetric matrix, Scaling matrices and counting the perfect matchings in graphs, A nondeterministic Turing machine variant to compute functions, Voting power on a graph connected political space with an application to decision-making in the council of the European Union, Computing the execution probability of jobs with replication in mixed-criticality schedules, Algorithms and complexity for Turaev-Viro invariants, Strong inconsistency, Complexity of fundamental problems in probabilistic abstract argumentation: beyond independence, On the complexity of inconsistency measurement, Matrix scaling and explicit doubly stochastic limits, Counting edge-injective homomorphisms and matchings on restricted graph classes, On the expected number of perfect matchings in cubic planar graphs, Distance spectrum, 1-factor and vertex-disjoint cycles, Approximate weighted model integration on DNF structures, On the normalized Laplacian permanental polynomial of a graph, Query answering over inconsistent knowledge bases: a probabilistic approach, Implicit recursion-theoretic characterizations of counting classes, On the permanental sum of graphs, Combinatorial properties of Farey graphs, Enumeration of perfect matchings of lattice graphs by Pfaffians, Colouring non-even digraphs, Oriented Euler complexes and signed perfect matchings, A complexity theory of constructible functions and sheaves, Construction of nonconvertible \((0,1)\) matrices, Noncommutativity makes determinants hard, Polynomial-time algorithms for quadratic isomorphism of polynomials: the regular case, Interlacing families. I: Bipartite Ramanujan graphs of all degrees, Limitations of sums of bounded read formulas and ABPs, A note on SpanP functions, On the relationship between \(\varepsilon\)-biased random variables and \(\varepsilon\)-dependent random variables, Random generation of combinatorial structures from a uniform distribution, Resolving contradictions: A plausible semantics for inconsistent systems, Simple characterizations of \(P(\# P)\) and complete problems, An analysis of Monte Carlo algorithms for counting problems, Symmetries of plane partitions and the permanent-determinant method, On the computational complexity of the order polynomial, Algorithms to count paths and cycles, Approximation to measurable functions and its relation to probabilistic computation, Locating \(P\)/poly optimally in the extended low hierarchy, NP is as easy as detecting unique solutions, The complexity of combinatorial problems with succinct input representation, The complexities of the coefficients of the Tutte polynomial, Graph embedding in SYNCHEM2, an expert system for organic synthesis discovery, Permanent and determinant, Some observations on the connection between counting and recursion, On the hardness of computing the permanent of random matrices, The complexity of optimization problems, Parallel computation with threshold functions, Recursion theoretic characterizations of complexity classes of counting functions, Feasible arithmetic computations: Valiant's hypothesis, On two extremal matrix problems, On the permanent of certain \((0,1)\) Toeplitz matrices, Approximate counting, uniform generation and rapidly mixing Markov chains, NC algorithms for computing the number of perfect matchings in \(K_{3,3}\)-free graphs and related problems, Towards a dichotomy theorem for the counting constraint satisfaction problem, A \(q\)-analog of approximation inclusion-exclusion, Computing the permanent by importance sampling method., Tensor network contractions for \#SAT, Comparison of permanental bounds of \((0,1)\)-matrices, Degree switching operations in networks and large scale systems assignment problems, Combinatorial problems over power sets, The complexity of power indexes with graph restricted coalitions, An efficient tree decomposition method for permanents and mixed discriminants, On efficient computation of the coefficients of some polynomials with applications to some enumeration problems, Pfaffian orientations, 0-1 permanents, and even cycles in directed graphs, Division in idealized unit cost RAMs, The complexity of determinacy problem on group testing, NP-completeness of some problems concerning voting games, On the complexity of ranking, Sparse complete sets for NP: solution of a conjecture of Berman and Hartmanis, The computational complexity of evolutionarily stable strategies, On counting problems and the polynomial-time hierarchy, Approximate inclusion-exclusion, New complexity results about Nash equilibria, The complexity of computing the number of strings of given length in context-free languages, Counting linear extensions, Restricted relativizations of probabilistic polynomial time, Turing machines with few accepting computations and low sets for PP, Polynomial-time 1-Turing reductions from \(\#\)PH to \(\#\)P, Generalizations of Opt P to the polynomial hierarchy, Generating all maximal induced subgraphs for hereditary and connected-hereditary graph properties, Counting propositional models, A note on the permanent value problem, Matching theory -- a sampler: From Dénes König to the present, On the power of enumerative counting, Approximating the permanent of graphs with large factors, A relationship between subpermanents and the arithmetic-geometric mean inequality, Exact algorithms for exact satisfiability and number of perfect matchings, On the counting complexity of propositional circumscription, A very hard log-space counting class, On the closure of certain function classes under integer division by polynomially-bounded functions, Counting feasible solutions of the traveling salesman problem with pickups and deliveries is \#\(P\)-complete, Robust self-assembly of graphs, On sparse hard sets for counting classes, Graph isomorphism is low for PP, On the autoreducibility of functions, The parameterized complexity of probability amplification, A note on \(\#\mathcal P\)-completeness of NP-witnessing relations, On the expressive power of permanents and perfect matchings of matrices of bounded pathwidth/cliquewidth, Counting complexity of propositional abduction, An efficient polynomial space and polynomial delay algorithm for enumeration of maximal motifs in a sequence, Efficiently computing the permanent and Hafnian of some banded Toeplitz matrices, The complexity of power-index comparison, Computing small partial coverings, Dimers on graphs in non-orientable surfaces, Inclusion-exclusion for \(k\)-CNF formulas, A note on the determinant and permanent problem, Nondeterministic \(NC^1\) computation, A lower bound for monotone arithmetic circuits computing \(0-1\) permanent, The determinant of a fuzzy matrix with respect to \(t\) and co-\(t\) norms, Exploration of NP-hard enumeration problems by simulated annealing -- the spectrum values of permanents, The counting complexity of a simple scheduling problem, On counting 3-D matchings of size \(k\), The three-color and two-color Tantrix\(^{\text{TM}}\) rotation puzzle problems are NP-complete via parsimonious reductions, Theory of one-tape linear-time Turing machines, Monomial bases for broken circuit complexes, Computing sparse permanents faster, On the computational complexity of reconstructing lattice sets from their \(X\)-rays, Inequalities and identities for generalized matrix functions, Graph isomorphism problem, The complexity of counting homeomorphs, On some natural complete operators, Gap-definable counting classes, PSPACE is provable by two provers in one round, Games against nature, Iterates of fuzzy circulant matrices, Extending matchings in graphs: A survey, Extending matchings in claw-free graphs, Expressing Polynomials as the Permanent of low rank Square Matrices, Counting with Combined Splitting and Capture–Recapture Methods, Algorithms and Complexity for Turaev-Viro Invariants, Computing the permanent modulo a prime power, A linear-optical proof that the permanent is # P -hard, Circuit lower bounds from learning-theoretic approaches, Satisfiability with index dependency, Monomials, multilinearity and identity testing in simple read-restricted circuits, Sampling Edge Covers in 3-Regular Graphs, A Dichotomy Theorem for Polynomial Evaluation, Relativized counting classes: Relations among thresholds, parity, and mods, Dempster's rule of combination is {\#}P-complete, Boolean circuits versus arithmetic circuits, State complexity and quantum computation, Counting lattice vectors, The Complexity of Computing the Random Priority Allocation Matrix, Phase transitions of PP-complete satisfiability problems, Singular values of Gaussian matrices and permanent estimators, The complexity of computational problems about Nash equilibria in symmetric win-lose games, The price of defense, Per-spectral characterizations of some edge-deleted subgraphs of a complete graph, NEW WORST-CASE UPPER BOUND FOR COUNTING EXACT SATISFIABILITY, Oblivious bounds on the probability of boolean functions, Evaluation and Enumeration Problems for Regular Path Queries, Pure Nash equilibria in a generalization of congestion games allowing resource failures, On the Complexity of Probabilistic Abstract Argumentation Frameworks, The complexity of regex crosswords, On the hardness of approximate reasoning, Algorithms for Propositional Model Counting, Visibility testing and counting for uncertain segments, Complexity and Algorithms for Well-Structured k-SAT Instances, A Tighter Bound for Counting Max-Weight Solutions to 2SAT Instances, On the Expressive Power of Permanents and Perfect Matchings of Matrices of Bounded Pathwidth/Cliquewidth (Extended Abstract), Perfect matchings on a type of lattices with toroidal boundary, Complexity of Counting the Optimal Solutions, On Listing, Sampling, and Counting the Chordal Graphs with Edge Constraints, Exponential lower bounds on the complexity of a class of dynamic programs for combinatorial optimization problems, Boson sampling with non-identical single photons, Probabilistic nonunitary gate in imaginary time evolution, Volume of convex polytopes equals mixed volume of simplices, Maximal independent sets in grid graphs, Barnette's conjecture through the lens of the \(Mod_k P\) complexity classes, Quantum circuits and low-degree polynomials over ${{\mathbb{F}}_\mathsf{2}}$, Some algebraic identities for the \({\alpha}\)-permanent, NIKE from affine determinant programs, The graph isomorphism problem and approximate categories, Enumeration of perfect matchings of the Cartesian products of graphs, Permanental partition models and Markovian Gibbs structures, A note on the permanental roots of bipartite graphs, Tropical bounds for eigenvalues of matrices, The Time Complexity of the Token Swapping Problem and Its Parallel Variants, Counting Minimal Dominating Sets, Subspace Arrangements, Graph Rigidity and Derandomization Through Submodular Optimization, Location of zeros for the partition function of the Ising model on bounded degree graphs, THE THOMPSON–HIGMAN MONOIDS M_k,i: THE ${\mathcal J}$-ORDER, THE ${\mathcal D}$-RELATION, AND THEIR COMPLEXITY, The Power of Self-Reducibility: Selectivity, Information, and Approximation, On the frontiers of polynomial computations in tropical geometry, Organization mechanism and counting algorithm on vertex-cover solutions, Identities between dimer partition functions on different surfaces, On variable-weighted exact satisfiability problems, CATEGORICAL COMPLEXITY, Solving \#SAT using vertex covers, An Extended Tree-Width Notion for Directed Graphs Related to the Computation of Permanents, The complexity of two problems on arithmetic circuits, Maximal Matching and Path Matching Counting in Polynomial Time for Graphs of Bounded Clique Width, Efficient computation of the permanent of a sparse matrix, Permanent Does Not Have Succinct Polynomial Size Arithmetic Circuits of Constant Depth, Algorithms for modular counting of roots of multivariate polynomials, Counting perfect matchings in \(n\)-extendable graphs, The complexity of ranking simple languages, Counting complexity classes for numeric computations. II: Algebraic and semialgebraic sets, Single-hook characters and hamiltonian circuits^∗, Graph Isomorphism is in SPP, Brace generation, Estimating the permanent by importance sampling from a finite population, A fast parametric assignment algorithm with applications in max-algebra, On the Complexity of Query Result Diversification, Poisson superposition processes, Computational aspects of mining maximal frequent patterns, On the complexity of computing Kostka numbers and Littlewood-Richardson coefficients, Pfaffian orientations and perfect matchings of scale-free networks, Bayesian incentive compatibility via matchings, Efficient learning algorithms yield circuit lower bounds, Permanental bounds for the signless Laplacian matrix of bipartite graphs and unicyclic graphs, A Complete Dichotomy Rises from the Capture of Vanishing Signatures, Solution-Graphs of Boolean Formulas and Isomorphism, Bravely, Moderately: A Common Theme in Four Recent Works, Complexity Theory Basics: NP and NL, Lower Bounds for the Determinantal Complexity of Explicit Low Degree Polynomials, Geometric complexity theory V: Efficient algorithms for Noether normalization, $$P\mathop{ =}\limits^{?}NP$$, Lower bounds for Pólya’s problem on permanent, Computing the Partition Function for Perfect Matchings in a Hypergraph, Subtractive reductions and complete problems for counting complexity classes, The permanental process, On the values of permanents of (0, 1) circulant matrices with three ones per row, Weighted enumeration of spanning subgraphs in locally tree-like graphs, A common algebraic description for probabilistic and quantum computations, Parameterized counting problems, Convertible andm-convertible matrices, UNIFORM CHARACTERIZATIONS OF COMPLEXITY CLASSES OF FUNCTIONS, Four Shorts Stories on Surprising Algorithmic Uses of Treewidth, The operators min and max on the polynomial hierarchy, Nonlevelable sets and immune sets in the accepting density hierarchy inNP, An information-theoretic treatment of random-self-reducibility, On the Permanental Polynomial and Permanental Sum of Signed Graphs, Majorization and the time complexity of linear optical networks, On the complexity of immanants, Unnamed Item, Hard Enumeration Problems in Geometry and Combinatorics, Unnamed Item, Approximating the permanent: A simple approach, Graph decompositions and tree automata in reasoning with uncertainty, Counting Small Induced Subgraphs Satisfying Monotone Properties, Holographic Algorithm with Matchgates Is Universal for Planar \#CSP over Boolean Domain, Unnamed Item, Singular spaces of matrices and their application in combinatorics, The Second Immanantal Polynomial and the Centroid of a Graph, Information and evidence in logic systems, Generalized theorems on relationships among reducibility notions to certain complexity classes, Structure and importance of logspace-MOD class, MAXIMUM MATCHINGS IN A PSEUDOFRACTAL SCALE-FREE WEB, Approximately Counting and Sampling Small Witnesses Using a Colorful Decision Oracle, Permutations with Restricted Displacement, Are there elimination algorithms for the permanent?, Revisiting Stochastic Loss Networks: Structures and Approximations, Counting single-qubit Clifford equivalent graph states is #P-complete, Some upper bounds for permanents of (0, 1)-matrices, Equations for secant varieties of Chow varieties, On the power of generalized Mod-classes, Is there an alternative to parsimonious semantics?, The complexity of counting problems in equational matching, Classifying the computational complexity of problems, Unnamed Item, Unnamed Item, Counting Integral Points in Polytopes via Numerical Analysis of Contour Integration, Solution Counting Algorithms for Constraint-Centered Search Heuristics, On the Representation of Symmetric and Antisymmetric Tensors, Counting Complexity of Minimal Cardinality and Minimal Weight Abduction, Computation of Exact Bootstrap Confidence Intervals: Complexity and Deterministic Algorithms, The Time Complexity of Permutation Routing via Matching, Token Swapping and a Variant, Some Completeness Results on Decision Trees and Group Testing, The Three-Color and Two-Color TantrixTM Rotation Puzzle Problems Are NP-Complete Via Parsimonious Reductions, Relationships among $PL$, $\#L$, and the determinant, On the Complexity of Holant Problems, Listing Maximal Subgraphs Satisfying Strongly Accessible Properties, Quantitative Automata under Probabilistic Semantics, Approximate reasoning with credible subsets, Non-deterministic Weighted Automata on Random Words, On the coefficients of the permanent and the determinant of a circulant matrix: Applications, Approximating permanents and hafnians, Characterizing optimal sampling of binary contingency tables via the configuration model, Unification algorithms cannot be combined in polynomial time, Federation and Navigation in SPARQL 1.1, Une dualité entre fonctions booléennes, NILPOTENT QUANTUM MECHANICS, On the Complexity of Convex Hulls of Subsets of the Two-Dimensional Plane, Optimization problem in multi-homogeneous homotopy method, Solving PP-Complete and #P-Complete Problems by P Systems with Active Membranes, Unnamed Item, Unnamed Item, Unnamed Item, Unnamed Item, Unnamed Item, Unnamed Item, Unnamed Item, On the parameterized complexity of approximate counting, Counting without sampling: Asymptotics of the log-partition function for certain statistical physics models, On the permanental nullity and matching number of graphs, No occurrence obstructions in geometric complexity theory, Unnamed Item, On the depth complexity of formulas, Graph characterization of fully indecomposable nonconvertible (0, 1)-matrices with minimal number of ones, An asymptotic approximation for the permanent of a doubly stochastic matrix, On the computational complexity of the Jones and Tutte polynomials, The regularity lemma is false over small fields, Unnamed Item, Unnamed Item, Weighted counting of solutions to sparse systems of equations, Graph isomorphism is low for PP, Computing permanents and counting Hamiltonian cycles by listing dissimilar vectors, Counting of Teams in First-Order Team Logics, Counting Perfect Matchings and the Switch Chain, On the classical complexity of sampling from quantum interference of indistinguishable bosons, The geometry of dimer models, On Proving Parameterized Size Lower Bounds for Multilinear Algebraic Models, Full Hermite interpolation of the reliability of a hammock network, The number of matchings in random graphs, Partitioning into Sets of Bounded Cardinality, Shortest Two Disjoint Paths in Polynomial Time, NC Algorithms for Computing a Perfect Matching and a Maximum Flow in One-Crossing-Minor-Free Graphs, Worst-Case Expected Shortfall with Univariate and Bivariate Marginals, Counting Restricted Homomorphisms via Möbius Inversion over Matroid Lattices, Unnamed Item, Counting Weighted Independent Sets beyond the Permanent, Solution-Graphs of Boolean Formulas and Isomorphism1, A Tight Analysis of Bethe Approximation for Permanent, EDGE DOMINATION NUMBER AND THE NUMBER OF MINIMUM EDGE DOMINATING SETS IN PSEUDOFRACTAL SCALE-FREE WEB AND SIERPIŃSKI GASKET, Lee–Yang zeros and the complexity of the ferromagnetic Ising model on bounded-degree graphs, Explaining by evidence, Tensors in computations, Completeness Results for Counting Problems with Easy Decision, Classification of a Class of Counting Problems Using Holographic Reductions, Extremal Graphs With a Given Number of Perfect Matchings, Phase Transitions for the Uniform Distribution in the Pattern Maximum Likelihood Problem and its Bethe Approximation, Uniform Determinantal Representations, Counting vertices of integral polytopes defined by facets, On the set of stable matchings in a bipartite graph, Disordered monomer-dimer model on cylinder graphs, On the roots of (signless) Laplacian permanental polynomials of graphs, Uniformly optimally reliable graphs: A survey, Inapproximability of positive semidefinite permanents and quantum state tomography, Parameterised counting in logspace, \texttt{QOptCraft}: a python package for the design and study of linear optical quantum systems, On counting propositional logic and Wagner's hierarchy, Kasteleyn cokernels and perfect matchings on planar bipartite graphs, Commuting quantum circuits and complexity of Ising partition functions, Sequential importance sampling for estimating expectations over the space of perfect matchings, Adjoint Majorana \(\mathrm{QCD}_2\) at finite \(N\), Perfect matching complexes of honeycomb graphs, A study on determination of some graphs by Laplacian and signless Laplacian permanental polynomials, The power of natural properties as oracles, Approximating the chromatic polynomial of a graph, Discrete Optimal Transport with Independent Marginals is #P-Hard, On the Parameterized Complexity of Counting Small-Sized Minimum \(\boldsymbol{(S,T)}\)-Cuts, COMBINATORIAL PROPERTIES FOR A CLASS OF SIMPLICIAL COMPLEXES EXTENDED FROM PSEUDO-FRACTAL SCALE-FREE WEB, Parameterized Counting and Cayley Graph Expanders, Projected model counting: beyond independent support, On measuring inconsistency in definite and indefinite databases with denial constraints, A Tutorial on Query Answering and Reasoning over Probabilistic Knowledge Bases, Strong simulation of linear optical processes, Efficient deterministic algorithms for embedding graphs on books, Inductive proof of Borchardt's theorem, Structure of single-peaked preferences, Zeros, chaotic ratios and the computational complexity of approximating the independence polynomial, Permanents of almost regular complete bipartite graphs, Interactions of computational complexity theory and mathematics, Picturing Counting Reductions with the ZH-Calculus, Diverse collections in matroids and graphs, Unnamed Item, Model Reductions for Inference: Generality of Pairwise, Binary, and Planar Factor Graphs, Leveraging Belief Propagation, Backtrack Search, and Statistics for Model Counting, On the Expressive Power of Planar Perfect Matching and Permanents of Bounded Treewidth Matrices, Faster Combinatorial Algorithms for Determinant and Pfaffian, ASYMPTOTIC EVALUATION OF BOSONIC PROBABILITY AMPLITUDES IN LINEAR UNITARY NETWORKS IN THE CASE OF LARGE NUMBER OF BOSONS, On the power of parity polynomial time, On the fixed parameter complexity of graph enumeration problems definable in monadic second-order logic, Holographic Algorithms with Matchgates Capture Precisely Tractable Planar #CSP, Algebraic independence in positive characteristic: A $p$-adic calculus, Counting classes: Thresholds, parity, mods, and fewness, Counting over non-planar graphs, On the hardness of the noncommutative determinant, On the Complexity of Computing Generators of Closed Sets, Clifford algebras and approximating the permanent, Graph classes and the switch Markov chain for matchings, Pure Nash equilibria in a generalization of congestion games allowing resource failures, The scaling mean and a law of large permanents, The Complexity of Symmetric Boolean Parity Holant Problems, Approximate set union via approximate randomization, Approximately Counting Embeddings into Random Graphs, Approximate set union via approximate randomization, Counting and enumeration complexity with application to multicriteria scheduling, Fixed Point Approximations for Retrial Networks, ON THE COMPLEXITY OF COUNTING FIXED POINTS AND GARDENS OF EDEN IN SEQUENTIAL DYNAMICAL SYSTEMS ON PLANAR BIPARTITE GRAPHS, Fast Computation by Block Permanents of Cumulative Distribution Functions of Order Statistics from Several Populations, FROM EQUIVALENCE TO ALMOST-EQUIVALENCE, AND BEYOND: MINIMIZING AUTOMATA WITH ERRORS, Characterizing properties of permanental polynomials of lollipop graphs, 2 × 2 Permanental Ideals of Hypermatrices, Matrix permanent and quantum entanglement of permutation invariant states, Sampling of bosonic qubits, Transducing Markov sequences, SELF-SPECIFYING MACHINES, THE OPERATORS MIN AND MAX ON THE POLYNOMIAL HIERARCHY, An algorithmic proof of Brégman–Minc theorem, Boolean Constraint Satisfaction Problems: When Does Post’s Lattice Help?, Faster than classical quantum algorithm for dense formulas of exact satisfiability and occupation problems, Towards quantum supremacy with lossy scattershot boson sampling, Gauges, loops, and polynomials for partition functions of graphical models, Rook Theory of the Finite General Linear Group, Unnamed Item, Boson-sampling with non-interacting fermions, Pfaffian Pairs and Parities: Counting on Linear Matroid Intersection and Parity Problems, Lifted Reasoning for Combinatorial Counting, Immanants of blocks from random matrices in some unitary ensembles

Cites Work

Retrieved from "https://portal.mardi4nfdi.de/w/index.php?title=Publication:600247&oldid=12488328"