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

(22)

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

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)