Lower bounds and separations for constant depth multilinear circuits
From MaRDI portal
Publication:626617
DOI10.1007/s00037-009-0270-8zbMath1213.68319MaRDI QIDQ626617
Publication date: 18 February 2011
Published in: Computational Complexity (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00037-009-0270-8
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
Related Items
Unnamed Item, Small-Depth Multilinear Formula Lower Bounds for Iterated Matrix Multiplication with Applications, On the Size of Homogeneous and of Depth-Four Formulas with Low Individual Degree, Unnamed Item, Unnamed Item, Unnamed Item, Unnamed Item, On the Size of Depth-Three Boolean Circuits for Computing Multilinear Functions, Barriers for Rank Methods in Arithmetic Complexity, A Quadratic Size-Hierarchy Theorem for Small-Depth Multilinear Formulas, On Expressing Majority as a Majority of Majorities, Towards Optimal Depth Reductions for Syntactically Multilinear Circuits, On the Symmetries of and Equivalence Test for Design Polynomials., A super-quadratic lower bound for depth four arithmetic circuits, Hitting-Sets for ROABP and Sum of Set-Multilinear Circuits, Approaching the Chasm at Depth Four, Lower bounds for special cases of syntactic multilinear ABPs, Non-commutative circuits and the sum-of-squares problem, Lower bounds for depth-three arithmetic circuits with small bottom fanin, Subexponential size hitting sets for bounded depth multilinear formulas, Arithmetic circuits: the chasm at depth four gets wider, Read-once polynomial identity testing, The NOF multiparty communication complexity of composed functions, Deterministic polynomial identity tests for multilinear bounded-read formulae, Deterministic identity testing for sum of read-once oblivious arithmetic branching programs, Multi-\(k\)-ic depth three circuit lower bound, Unbalancing sets and an almost quadratic lower bound for syntactically multilinear arithmetic circuits, Average-case linear matrix factorization and reconstruction of low width algebraic branching programs, Slightly improved lower bounds for homogeneous formulas of bounded depth and bounded individual degree, Lower bounds and PIT for non-commutative arithmetic circuits with restricted parse trees, Unifying known lower bounds via geometric complexity theory, Algebraic Complexity Classes, A Selection of Lower Bounds for Arithmetic Circuits, Uniform derandomization from pathetic lower bounds, Lower Bounds for Depth-4 Formulas Computing Iterated Matrix Multiplication, An Exponential Lower Bound for Homogeneous Depth Four Arithmetic Formulas, Permanent Does Not Have Succinct Polynomial Size Arithmetic Circuits of Constant Depth, Simulation of Arithmetical Circuits by Branching Programs with Preservation of Constant Width and Syntactic Multilinearity, Small-depth Multilinear Formula Lower Bounds for Iterated Matrix Multiplication, with Applications.
