Separating multilinear branching programs and formulas

DOI10.1145/2213977.2214034zbMath1286.68131OpenAlexW2071105597MaRDI QIDQ5415505

Sylvain Perifel, Zeev Dvir, Amir Yehudayoff, Guillaume Malod

Publication date: 13 May 2014

Published in: Proceedings of the forty-fourth annual ACM symposium on Theory of computing (Search for Journal in Brave)

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

zbMATH Keywords

polynomialsalgebraic branching programsarithmetic circuitsarithmetic formulasmultilinear computations

Mathematics Subject Classification ID

Related Items (17)

Geometric aspects of iterated matrix multiplication ⋮ Quadratic lower bounds for algebraic branching programs and formulas ⋮ Small-depth Multilinear Formula Lower Bounds for Iterated Matrix Multiplication, with Applications. ⋮ Lower Bounds for Depth-4 Formulas Computing Iterated Matrix Multiplication ⋮ Dimension of tensor network varieties ⋮ \textsf{VNP} = \textsf{VP} in the multilinear world ⋮ A Quadratic Size-Hierarchy Theorem for Small-Depth Multilinear Formulas ⋮ Small-Depth Multilinear Formula Lower Bounds for Iterated Matrix Multiplication with Applications ⋮ Unnamed Item ⋮ Lower bounds for special cases of syntactic multilinear ABPs ⋮ Lower bounds for arithmetic circuits via the Hankel matrix ⋮ Algebraic Complexity Classes ⋮ A quadratic lower bound for algebraic branching programs ⋮ A super-quadratic lower bound for depth four arithmetic circuits ⋮ Lower bounds and PIT for non-commutative arithmetic circuits with restricted parse trees ⋮ The linear span of uniform matrix product states ⋮ Limitations of sums of bounded read formulas and ABPs

This page was built for publication: Separating multilinear branching programs and formulas