The complexity of tensor calculus

DOI10.1007/S00037-000-0170-4MaRDI QIDQ1413648zbMATH OpenOpenAlexFDO

Authors Carsten Damm, Pierre McKenzie, Markus Holzer

Publication date 17 November 2003

Published in Computational Complexity (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00037-000-0170-4

zbMATH Keywords

multilinear algebracomplexitycompletenesspermanenttensor calculusword problemBoolean semiringpolytime algorithmcounting classesalgebraic Turing machineTensor formula

Mathematics Subject Classification ID

Multilinear algebra, tensor calculus (15A69) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Algebraic theory of languages and automata (68Q70) Combinatorics on words (68R15) Turing machines and related notions (03D10) Word problems, etc. in computability and recursion theory (03D40)

Recommendations

• The complexity of tensor circuit evaluation
• scientific article; zbMATH DE number 1834647
• The arithmetic complexity of tensor contraction
• The arithmetic complexity of tensor contractions
• Circuits arithmétiques et calculs tensoriels

Cited in

(25)

• The arithmetic complexity of tensor contraction
• Tensor products and computability
• New Algorithm for Tensor Calculation in Field Theories
• On the Complexity of Isomorphism Problems for Tensors, Groups, and Polynomials I: Tensor Isomorphism-Completeness
• A common algebraic description for probabilistic and quantum computations
• Most tensor problems are NP-hard
• Tensor network complexity of multilinear maps
• Tensor network contractions for \#SAT
• Algorithmic simplification of tensor expressions
• Logical characterizations of weighted complexity classes
• scientific article; zbMATH DE number 1834647 (Why is no real title available?)
• Generalized counting constraint satisfaction problems with determinantal circuits
• Theory and Computation of Complex Tensors and its Applications
• The tensor hierarchy simplified
• Picturing Counting Reductions with the ZH-Calculus
• The arithmetic complexity of tensor contractions
• Characterizing Valiant's algebraic complexity classes
• Tensor network rewriting strategies for satisfiability and counting
• Well-tempered ZX and ZH calculi
• Weighted automata and logics meet computational complexity
• Descriptive complexity and weighted Turing machines
• The complexity of tensor circuit evaluation
• Length Complexity of Tensor Products
• Tensors masquerading as matchgates: relaxing planarity restrictions on Pfaffian circuits
• A graphical \#SAT algorithm for formulae with small clause density

This page was built for publication: The complexity of tensor calculus

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1413648)