A computational proof of complexity of some restricted counting problems
From MaRDI portal
Publication:534558
DOI10.1016/J.TCS.2010.10.039zbMATH Open1216.68122OpenAlexW2099255094MaRDI QIDQ534558FDOQ534558
Authors: Jin-Yi Cai, Pinyan Lu, Mingji Xia 
Publication date: 18 May 2011
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2010.10.039
Recommendations
Analysis of algorithms and problem complexity (68Q25) Signed and weighted graphs (05C22) Software, source code, etc. for problems pertaining to computer science (68-04)
Cites Work
- On the complexity of H-coloring
- The complexity of partition functions
- Complexity classifications of Boolean constraint satisfaction problems
- On counting homomorphisms to directed acyclic graphs
- Title not available (Why is that?)
- Holant problems and counting CSP
- Title not available (Why is that?)
- Towards a dichotomy theorem for the counting constraint satisfaction problem
- Complexity of generalized satisfiability counting problems
- Title not available (Why is that?)
- Quantum Circuits That Can Be Simulated Classically in Polynomial Time
- The complexity of counting in sparse, regular, and planar graphs
- Title not available (Why is that?)
- Graph homomorphisms with complex values: a dichotomy theorem (extended abstract)
- A complexity dichotomy for partition functions with mixed signs
- Holographic algorithms: from art to science
- A Computational Proof of Complexity of Some Restricted Counting Problems
- Title not available (Why is that?)
Cited In (12)
- A dichotomy for real weighted Holant problems
- On the Complexity of Holant Problems
- Title not available (Why is that?)
- From Holant to \#CSP and back: dichotomy for Holant\(^{c}\) problems
- Holant problems for 3-regular graphs with complex edge functions
- Partition functions on \(k\)-regular graphs with \(\{0,1\}\)-vertex assignments and real edge functions
- Spin systems on \(k\)-regular graphs with complex edge functions
- A complete dichotomy rises from the capture of vanishing signatures
- A Computational Proof of Complexity of Some Restricted Counting Problems
- Holographic reduction, interpolation and hardness
- AntiFactor is FPT parameterized by treewidth and list size (but counting is hard)
- Computational complexity of counting problems on 3-regular planar graphs
This page was built for publication: A computational proof of complexity of some restricted counting problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q534558)
