Improved Bounds for Reduction to Depth 4 and Depth 3

DOI10.1007/978-3-642-40313-2_71zbMath1360.68484arXiv1304.5777OpenAlexW1508771701MaRDI QIDQ2849964

Sébastien Tavenas

Publication date: 20 September 2013

Published in: Mathematical Foundations of Computer Science 2013 (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Related Items (22)

Lower Bounds for Sums of Powers of Low Degree Univariates ⋮ Lower bounds for depth-three arithmetic circuits with small bottom fanin ⋮ Subexponential size hitting sets for bounded depth multilinear formulas ⋮ On the limits of depth reduction at depth 3 over small finite fields ⋮ The Shifted Partial Derivative Complexity of Elementary Symmetric Polynomials ⋮ Log-Concavity and Lower Bounds for Arithmetic Circuits ⋮ Lower Bounds for Depth-4 Formulas Computing Iterated Matrix Multiplication ⋮ Multi-\(k\)-ic depth three circuit lower bound ⋮ Equations for secant varieties of Chow varieties ⋮ An Exponential Lower Bound for Homogeneous Depth Four Arithmetic Formulas ⋮ On the Power of Homogeneous Depth 4 Arithmetic Circuits ⋮ Lower bounds by Birkhoff interpolation ⋮ Unnamed Item ⋮ Depth-4 lower bounds, determinantal complexity: a unified approach ⋮ Average-case linear matrix factorization and reconstruction of low width algebraic branching programs ⋮ Arithmetic Circuits: A Chasm at Depth 3 ⋮ Algebraic Complexity Classes ⋮ A Selection of Lower Bounds for Arithmetic Circuits ⋮ Approaching the Chasm at Depth Four ⋮ A \(\tau \)-conjecture for Newton polygons ⋮ Geometric complexity theory: an introduction for geometers ⋮ Unifying known lower bounds via geometric complexity theory

This page was built for publication: Improved Bounds for Reduction to Depth 4 and Depth 3