Classification of a Class of Counting Problems Using Holographic Reductions
type: Item
instance of: scholarly article
title: Classification of a Class of Counting Problems Using Holographic Reductions
zbMATH Open document ID: 1248.68208
DOI: 10.1007/978-3-642-02882-3_47
author: Michael Kowalczyk
published in: Lecture Notes in Computer Science
publication date: 2009-07-23T00:00:00Z
Mathematics Subject Classification ID: 68Q15
Mathematics Subject Classification ID: 05C30
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 5585647
zbMATH Keywords: Fibonacci gates
zbMATH Keywords: holographic algorithms
zbMATH Keywords: holographic reduction
zbMATH Keywords: interpolation
MaRDI profile type: MaRDI publication profile
full work available at URL: 978-3-642-02882-3 47
OpenAlex ID: W1559830925
cites work: Towards a dichotomy theorem for the counting constraint satisfaction problem
cites work: The complexity of partition functions
cites work: Q3549638
cites work: On Symmetric Signatures in Holographic Algorithms
cites work: Holant problems and counting CSP
cites work: Complexity of generalized satisfiability counting problems
cites work: Complexity classifications of Boolean constraint satisfaction problems
cites work: Tensor Geometry
cites work: The Complexity of Weighted Boolean #CSP
cites work: On counting homomorphisms to directed acyclic graphs
cites work: Q4521549
cites work: Reflection positivity, rank connectivity, and homomorphism of graphs
cites work: Q5390002
cites work: The complexity of choosing an H -colouring (nearly) uniformly at random
cites work: Duality and Polynomial Testing of Tree Homomorphisms
cites work: The statistics of dimers on a lattice. I: The number of dimer arrangements on a quadratic lattice
cites work: Q5605168
cites work: Operations with structures
cites work: Dimer problem in statistical mechanics-an exact result
cites work: The complexity of counting in sparse, regular, and planar graphs
cites work: The complexity of computing the permanent
cites work: Quantum Circuits That Can Be Simulated Classically in Polynomial Time
description: scientific article; zbMATH DE number 5585647