Holographic reduction: a domain changed application and its partial converse theorems

DOI10.1007/978-3-642-14165-2_56MaRDI QIDQ3587417zbMATH OpenOpenAlexFDO

Authors Mingji Xia

Publication date 7 September 2010

Published in Automata, Languages and Programming (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-14165-2_56

zbMATH Keywords

\#BCSP\#CSPgraph homomorphismholant problemholographic reduction

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• From Holant to \#CSP and back: dichotomy for Holant\(^{c}\) problems
• From Holant to \#CSP and back: dichotomy for Holant\(^{c }\) problems
• Holant problems and counting CSP
• Holographic reduction for some counting problems
• Holographic reduction, interpolation and hardness

Cited in

(4)

• Geometric analogue of holographic reduced representation
• Holographic reduction for some counting problems
• Bipartite 3-regular counting problems with mixed signs
• Bounded degree nonnegative counting CSP

This page was built for publication: Holographic reduction: a domain changed application and its partial converse theorems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3587417)