The Complexity of Symmetric Boolean Parity Holant Problems

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

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (max. 100)

A collapse theorem for holographic algorithms with matchgates on domain size at most 4

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

This page was built for publication: The Complexity of Symmetric Boolean Parity Holant Problems