The arithmetic complexity of tensor contraction

DOI10.1007/S00224-015-9630-8MaRDI QIDQ290898zbMATHOpenAlexFDO

Authors Florent Capelli, Arnaud Durand, Stefan Mengel

Publication date 3 June 2016

Published in Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00224-015-9630-8

zbMATH Keywords

arithmetic circuitstensor calculusalgebraic complexity

Mathematics Subject Classification ID

Multilinear algebra, tensor calculus (15A69) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Recommendations

• The arithmetic complexity of tensor contractions
• The complexity of tensor calculus
• Most tensor problems are NP-hard
• Circuits arithmétiques et calculs tensoriels
• scientific article; zbMATH DE number 1834647

Cites work

• scientific article; zbMATH DE number 3445419 (Why is no real title available?)
• Arithmetic branching programs with memory
• Arithmetic circuits: the chasm at depth four gets wider
• Characterizing Arithmetic Circuit Classes by Constraint Satisfaction Problems
• Characterizing Valiant's algebraic complexity classes
• Circuits arithmétiques et calculs tensoriels
• Completeness and reduction in algebraic complexity theory
• Fast Parallel Computation of Polynomials Using Few Processors
• Problems complete for deterministic logarithmic space
• The complexity of acyclic conjunctive queries
• The complexity of tensor calculus
• The complexity of tensor circuit evaluation
• The complexity of weighted counting for acyclic conjunctive queries
• The descriptive complexity approach to LOGCFL

Cited in

(10)

• Length Complexity of Tensor Products
• Strassen's Algorithm for Tensor Contraction
• scientific article; zbMATH DE number 1834647 (Why is no real title available?)
• Algorithmic simplification of tensor expressions
• An algorithm to simplify tensor expressions
• Tensor network complexity of multilinear maps
• Circuits arithmétiques et calculs tensoriels
• The complexity of tensor circuit evaluation
• The complexity of tensor calculus
• The arithmetic complexity of tensor contractions

This page was built for publication: The arithmetic complexity of tensor contraction

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