Depth-4 Lower Bounds, Determinantal Complexity : A Unified Approach

DOI10.4230/LIPIcs.STACS.2014.239zbMath1359.68123arXiv1308.1640OpenAlexW2964011532MaRDI QIDQ2965487

Partha Mukhopadhyay, Suryajith Chillara

Publication date: 3 March 2017

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

zbMATH Keywords

arithmetic circuitsdeterminantal complexitydepth-4 lower bounds

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Determinants, permanents, traces, other special matrix functions (15A15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (8)

The Limits of Depth Reduction for Arithmetic Formulas: It's All About the Top Fan-In ⋮ On the limits of depth reduction at depth 3 over small finite fields ⋮ Lower Bounds for Depth-4 Formulas Computing Iterated Matrix Multiplication ⋮ On the Power of Homogeneous Depth 4 Arithmetic Circuits ⋮ The Computational Power of Depth Five Arithmetic Circuits ⋮ On the Size of Homogeneous and of Depth-Four Formulas with Low Individual Degree ⋮ A Selection of Lower Bounds for Arithmetic Circuits ⋮ On the Symmetries of and Equivalence Test for Design Polynomials.

This page was built for publication: Depth-4 Lower Bounds, Determinantal Complexity : A Unified Approach