Some lower bound results for set-multilinear arithmetic computations

DOI10.4086/CJTCS.2016.006zbMATH Open1358.68109OpenAlexW4250280356MaRDI QIDQ2808533FDOQ2808533

Authors Vikraman Arvind, S. Raja

Publication date 24 May 2016

Published in Chicago Journal of Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1511.02308

zbMATH Keywords

lower boundspolynomialsROABPsset-multilinear

Mathematics Subject Classification ID

Symbolic computation and algebraic computation (68W30) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Determinants, permanents, traces, other special matrix functions (15A15)

Recommendations

• A Lower Bound for the Size of Syntactically Multilinear Arithmetic Circuits
• Unbalancing sets and an almost quadratic lower bound for syntactically multilinear arithmetic circuits
• scientific article; zbMATH DE number 7250151
• Set-multilinear and non-commutative formula lower bounds for iterated matrix multiplication
• A Selection of Lower Bounds for Arithmetic Circuits
• scientific article; zbMATH DE number 806753
• scientific article; zbMATH DE number 1351079
• Publication:4886070
• Lower bounds in algebraic computational complexity
• Lower bounds on the depth of monotone arithmetic computations

Cites work

• Balancing syntactically multilinear arithmetic circuits

Cited in

(11)

• On the hardness of the determinant: sum of regular set-multilinear circuits
• Limitations of sums of bounded read formulas and ABPs
• scientific article; zbMATH DE number 7561311 (Why is no real title available?)
• Lower bounds for arithmetic circuits via the Hankel matrix
• On proving parameterized size lower bounds for multilinear algebraic models
• On proving parameterized size lower bounds for multilinear algebraic models
• scientific article; zbMATH DE number 7561696 (Why is no real title available?)
• Lower bounds for special cases of syntactic multilinear ABPs
• scientific article; zbMATH DE number 7204372 (Why is no real title available?)
• Lower bounds for the sum of small-size algebraic branching programs
• Lower bounds for special cases of syntactic multilinear ABPs

This page was built for publication: Some lower bound results for set-multilinear arithmetic computations

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