Holographic algorithms by Fibonacci gates
From MaRDI portal
Publication:1931762
DOI10.1016/j.laa.2011.02.032zbMath1257.05004OpenAlexW2031917338MaRDI QIDQ1931762
Pinyan Lu, Jin-Yi Cai, Mingji Xia
Publication date: 16 January 2013
Published in: Linear Algebra and its Applications (Search for Journal in Brave)
Full work available at URL: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.221.1824
Exact enumeration problems, generating functions (05A15) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
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 Algorithm with Matchgates Is Universal for Planar \#CSP over Boolean Domain, Holographic algorithms without matchgates, Holographic reduction for some counting problems, The computational complexity of Holant problems on 3-regular graphs, Holographic algorithms beyond matchgates, On the Complexity of Holant Problems, Characterizing partition functions of the edge-coloring model by rank growth, Holographic algorithms on bases of rank 2, The complexity of planar Boolean \#CSP with complex weights, Clifford gates in the Holant framework, A Complete Dichotomy Rises from the Capture of Vanishing Signatures, Counting Restricted Homomorphisms via Möbius Inversion over Matroid Lattices, A dichotomy for real weighted Holant problems
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- The complexity of computing the permanent
- Basis collapse in holographic algorithms
- Holographic algorithms: the power of dimensionality resolved
- Complexity of generalized satisfiability counting problems
- Valiant's holant theorem and matchgate tensors
- Computational complexity of counting problems on 3-regular planar graphs
- The Complexity of Counting in Sparse, Regular, and Planar Graphs
- The statistics of dimers on a lattice
- Quantum Circuits That Can Be Simulated Classically in Polynomial Time
- Holographic Algorithms
- Some Results on Matchgates and Holographic Algorithms
- The Complexity of Enumeration and Reliability Problems
- Tensor Geometry
- Holant problems and counting CSP
- Dimer problem in statistical mechanics-an exact result
- Holographic Algorithms with Matchgates Capture Precisely Tractable Planar #CSP
