Lower bounds and separations for constant depth multilinear circuits

DOI10.1007/s00037-009-0270-8zbMath1213.68319OpenAlexW2172394696MaRDI QIDQ626617

Amir Yehudayoff, Ran Raz

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

zbMATH Keywords

separationsarithmetic circuitsconstant depth circuits

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (39)

Lower bounds for depth-three arithmetic circuits with small bottom fanin ⋮ Subexponential size hitting sets for bounded depth multilinear formulas ⋮ Uniform derandomization from pathetic lower bounds ⋮ Small-depth Multilinear Formula Lower Bounds for Iterated Matrix Multiplication, with Applications. ⋮ On the Size of Depth-Three Boolean Circuits for Computing Multilinear Functions ⋮ Lower Bounds for Depth-4 Formulas Computing Iterated Matrix Multiplication ⋮ Deterministic identity testing for sum of read-once oblivious arithmetic branching programs ⋮ Multi-\(k\)-ic depth three circuit lower bound ⋮ Deterministic polynomial identity tests for multilinear bounded-read formulae ⋮ An Exponential Lower Bound for Homogeneous Depth Four Arithmetic Formulas ⋮ Unbalancing sets and an almost quadratic lower bound for syntactically multilinear arithmetic circuits ⋮ Arithmetic circuits: the chasm at depth four gets wider ⋮ Unnamed Item ⋮ Barriers for Rank Methods in Arithmetic Complexity ⋮ A Quadratic Size-Hierarchy Theorem for Small-Depth Multilinear Formulas ⋮ Read-once polynomial identity testing ⋮ The NOF multiparty communication complexity of composed functions ⋮ Permanent Does Not Have Succinct Polynomial Size Arithmetic Circuits of Constant Depth ⋮ Small-Depth Multilinear Formula Lower Bounds for Iterated Matrix Multiplication with Applications ⋮ Unnamed Item ⋮ Average-case linear matrix factorization and reconstruction of low width algebraic branching programs ⋮ Lower bounds for special cases of syntactic multilinear ABPs ⋮ Non-commutative circuits and the sum-of-squares problem ⋮ Slightly improved lower bounds for homogeneous formulas of bounded depth and bounded individual degree ⋮ On the Size of Homogeneous and of Depth-Four Formulas with Low Individual Degree ⋮ On Expressing Majority as a Majority of Majorities ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Algebraic Complexity Classes ⋮ A Selection of Lower Bounds for Arithmetic Circuits ⋮ Simulation of Arithmetical Circuits by Branching Programs with Preservation of Constant Width and Syntactic Multilinearity ⋮ 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 ⋮ Unnamed Item ⋮ Lower bounds and PIT for non-commutative arithmetic circuits with restricted parse trees ⋮ Approaching the Chasm at Depth Four ⋮ Hitting-Sets for ROABP and Sum of Set-Multilinear Circuits ⋮ Unifying known lower bounds via geometric complexity theory

This page was built for publication: Lower bounds and separations for constant depth multilinear circuits