Holographic reduction, interpolation and hardness

DOI10.1007/s00037-012-0044-6zbMath1282.68120MaRDI QIDQ1926111

Mingji Xia, Pinyan Lu, Jin-Yi Cai

Publication date: 27 December 2012

Published in: Computational Complexity (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00037-012-0044-6

zbMATH Keywords

polynomial interpolation; counting complexity; holographic reduction; P-hard

Mathematics Subject Classification ID

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

Related Items

The complexity of counting edge colorings and a dichotomy for some higher domain Holant problems, Holant problems for 3-regular graphs with complex edge functions, Holographic algorithms beyond matchgates, The complexity of Bayesian networks specified by propositional and relational languages, The complexity of planar Boolean \#CSP with complex weights, A Complete Dichotomy Rises from the Capture of Vanishing Signatures

Cites Work

• Unnamed Item
• Unnamed Item
• A computational proof of complexity of some restricted counting problems
• The complexity of computing the permanent
• Holographic algorithms: from art to science
• Spin systems on \(k\)-regular graphs with complex edge functions
• Towards a dichotomy theorem for the counting constraint satisfaction problem
• On symmetric signatures in holographic algorithms
• Approximating the permanent of graphs with large factors
• The complexity of counting colourings and independent sets in sparse graphs and hypergraphs
• Valiant's holant theorem and matchgate tensors
• Computational complexity of counting problems on 3-regular planar graphs
• The complexity of partition functions
• The Complexity of Counting in Sparse, Regular, and Planar Graphs
• On the complexity of #CSP
• The statistics of dimers on a lattice
• From Holant to #CSP and Back: Dichotomy for Holant c Problems
• Computational Complexity of Holant Problems
• The Complexity of the Counting Constraint Satisfaction Problem
• Holographic Algorithms
• On counting homomorphisms to directed acyclic graphs
• A Dichotomy for k-Regular Graphs with {0, 1}-Vertex Assignments and Real Edge Functions
• The Complexity of Enumeration and Reliability Problems
• Holant problems and counting CSP
• Dimer problem in statistical mechanics-an exact result