The Complexity of Symmetric Boolean Parity Holant Problems
From MaRDI portal
Publication:5892610
DOI10.1007/978-3-642-22006-7_60zbMath1333.68144OpenAlexW1271872764MaRDI QIDQ5892610
Heng Guo, Pinyan Lu, Leslie G. Valiant
Publication date: 6 July 2011
Published in: Automata, Languages and Programming (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-642-22006-7_60
Analysis of algorithms and problem complexity (68Q25) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Related Items
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- The complexity of computing the permanent
- NP is as easy as detecting unique solutions
- Complexity of generalized satisfiability counting problems
- Graph Isomorphism is in SPP
- Complexity Classifications of Boolean Constraint Satisfaction Problems
- From Holant to #CSP and Back: Dichotomy for Holant c Problems
- Holant Problems for Regular Graphs with Complex Edge Functions
- Quantum Circuits That Can Be Simulated Classically in Polynomial Time
- The Complexity of the Counting Constraint Satisfaction Problem
- Holographic Algorithms
- A dichotomy theorem for constraint satisfaction problems on a 3-element set
- On counting homomorphisms to directed acyclic graphs
- Some Observations on Holographic Algorithms
- Signature Theory in Holographic Algorithms
- A Computational Proof of Complexity of Some Restricted Counting Problems
- The Complexity of Weighted Boolean #CSP
- Counting Classes are at Least as Hard as the Polynomial-Time Hierarchy
- Tensor Geometry
- On the Structure of Polynomial Time Reducibility
- The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
- Holant problems and counting CSP
- The complexity of satisfiability problems
- Holographic Algorithms with Matchgates Capture Precisely Tractable Planar #CSP
- Graph Homomorphisms with Complex Values: A Dichotomy Theorem
