Separating multilinear branching programs and formulas
From MaRDI portal
Publication:5415505
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
polynomialsalgebraic branching programsarithmetic circuitsarithmetic formulasmultilinear computations
Lua error in Module:PublicationMSCList at line 37: attempt to index local 'msc_result' (a nil value).
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
