The arithmetic complexity of tensor contractions

Authors Florent Capelli, Arnaud Durand, Stefan Mengel



PDF
Thumbnail PDF

File

LIPIcs.STACS.2013.365.pdf
  • Filesize: 0.59 MB
  • 12 pages

Document Identifiers

Author Details

Florent Capelli
Arnaud Durand
Stefan Mengel

Cite AsGet BibTex

Florent Capelli, Arnaud Durand, and Stefan Mengel. The arithmetic complexity of tensor contractions. In 30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013). Leibniz International Proceedings in Informatics (LIPIcs), Volume 20, pp. 365-376, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)
https://doi.org/10.4230/LIPIcs.STACS.2013.365

Abstract

We investigate the algebraic complexity of tensor calulus. We consider a generalization of iterated matrix product to tensors and show that the resulting formulas exactly capture VP, the class of polynomial families efficiently computable by arithmetic circuits. This gives a natural and robust characterization of this complexity class that despite its naturalness is not very well understood so far.
Keywords
  • algebraic complexity
  • arithmetic circuits
  • tensor calculus

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail