Generalized counting constraint satisfaction problems with determinantal circuits

DOI10.1016/j.laa.2014.09.050zbMath1302.05108arXiv1302.1932MaRDI QIDQ472444

Jason Morton, Jacob M. Turner

Publication date: 19 November 2014

Published in: Linear Algebra and its Applications (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1302.1932

zbMATH Keywords

monoidal categoriescounting complexitytensor network

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

05C31: Graph polynomials

15A15: Determinants, permanents, traces, other special matrix functions

15A24: Matrix equations and identities

05C50: Graphs and linear algebra (matrices, eigenvalues, etc.)

15A69: Multilinear algebra, tensor calculus

Related Items

Computing the Tutte polynomial of lattice path matroids using determinantal circuits, Tensor network contractions for \#SAT, Polynomial-time solvable \(\#\)CSP problems via algebraic models and Pfaffian circuits, A finite-tame-wild trichotomy theorem for tensor diagrams

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Computing the Tutte polynomial of lattice path matroids using determinantal circuits
• The geometry of tensor calculus. I
• Towards an algebraic theory of Boolean circuits.
• The complexity of tensor calculus
• Lattice path matroids: Enumerative aspects and Tutte polynomials
• A combinatorial Laplacian with vertex weights
• Holographic algorithms without matchgates
• Geometric Complexity Theory I: An Approach to thePvs.NPand Related Problems
• Categorical quantum circuits
• Quantum Circuits That Can Be Simulated Classically in Polynomial Time
• The Complexity of the Counting Constraint Satisfaction Problem
• Traced monoidal categories
• Belief propagation in monoidal categories
• Multi-Path Matroids
• Computational Complexity
• Complexity of counting CSP with complex weights