Depth-4 Lower Bounds, Determinantal Complexity : A Unified Approach
From MaRDI portal
Publication:2965487
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
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
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.
