Holographic reduction, interpolation and hardness
type: Item
instance of: scholarly article
title: Holographic reduction, interpolation and hardness
zbMATH Open document ID: 1282.68120
author: Jin-Yi Cai
author: Pinyan Lu
author: Mingji Xia
published in: Computational Complexity
publication date: 2012-12-27T00:00:00Z
Mathematics Subject Classification ID: 68Q17
zbMATH DE Number: 6118608
zbMATH Keywords: holographic reduction
zbMATH Keywords: polynomial interpolation
zbMATH Keywords: P-hard
zbMATH Keywords: counting complexity
MaRDI profile type: Publication
full work available at URL: s00037-012-0044-6
OpenAlex ID: W2064541898
cites work: The Complexity of the Counting Constraint Satisfaction Problem
cites work: Towards a dichotomy theorem for the counting constraint satisfaction problem
cites work: The complexity of partition functions
cites work: Valiant's holant theorem and matchgate tensors
cites work: From Holant to #CSP and Back: Dichotomy for Holant c Problems
cites work: A Dichotomy for k-Regular Graphs with {0, 1}-Vertex Assignments and Real Edge Functions
cites work: Spin systems on \(k\)-regular graphs with complex edge functions
cites work: On symmetric signatures in holographic algorithms
cites work: Holographic algorithms: from art to science
cites work: Holant problems and counting CSP
cites work: Computational Complexity of Holant Problems
cites work: A computational proof of complexity of some restricted counting problems
cites work: Approximating the permanent of graphs with large factors
cites work: On counting homomorphisms to directed acyclic graphs
cites work: Q4521549
cites work: On the complexity of \#CSP
cites work: The complexity of counting colourings and independent sets in sparse graphs and hypergraphs
cites work: The statistics of dimers on a lattice. I: The number of dimer arrangements on a quadratic lattice
cites work: Holant Problems for Regular Graphs with Complex Edge Functions
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: The Complexity of Enumeration and Reliability Problems
cites work: Holographic Algorithms
cites work: Computational complexity of counting problems on 3-regular planar graphs
DOI: 10.1007/S00037-012-0044-6
description: scientific article; zbMATH DE number 6118608