Tensor-Rank and Lower Bounds for Arithmetic Formulas

DOI10.1145/2535928zbMath1281.68136OpenAlexW1988738948MaRDI QIDQ5395735

Ran Raz

Publication date: 17 February 2014

Published in: Journal of the ACM (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/2535928

zbMATH Keywords

lower boundstensor rankarithmetic circuitsmultilinear circuitshomogenous circuits

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Symbolic computation and algebraic computation (68W30) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (15)

A separation between tropical matrix ranks ⋮ Abelian tensors ⋮ Characterizing Propositional Proofs as Noncommutative Formulas ⋮ Small-depth Multilinear Formula Lower Bounds for Iterated Matrix Multiplication, with Applications. ⋮ Weighted slice rank and a minimax correspondence to Strassen's spectra ⋮ Unnamed Item ⋮ Small-Depth Multilinear Formula Lower Bounds for Iterated Matrix Multiplication with Applications ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ On the Size of Homogeneous and of Depth-Four Formulas with Low Individual Degree ⋮ Arithmetic Circuits: A Chasm at Depth 3 ⋮ Maximum Waring Ranks of Monomials and Sums of Coprime Monomials ⋮ Unnamed Item ⋮ A super-quadratic lower bound for depth four arithmetic circuits

This page was built for publication: Tensor-Rank and Lower Bounds for Arithmetic Formulas