Depth-4 lower bounds, determinantal complexity: a unified approach
DOI10.1007/s00037-019-00185-4zbMath1498.68124OpenAlexW2946971814MaRDI QIDQ2281250
Suryajith Chillara, Partha Mukhopadhyay
Publication date: 19 December 2019
Published in: Computational Complexity (Search for Journal in Brave)
Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2014/4461/
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) Networks and circuits as models of computation; circuit complexity (68Q06)
Related Items (1)
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Arithmetic circuits: the chasm at depth four gets wider
- Lower bounds for the determinantal complexity of explicit low degree polynomials
- Permanent and determinant
- On two extremal matrix problems
- A note on the determinant and permanent problem
- Hardness vs randomness
- Improved Bounds for Reduction to Depth 4 and Depth 3
- An Exponential Lower Bound for Homogeneous Depth Four Arithmetic Formulas
- A Lower Bound for the Formula Size of Rational Functions
- Representations and Parallel Computations for Rational Functions
- Superpolynomial Lower Bounds for General Homogeneous Depth 4 Arithmetic Circuits
- Lower bounds for depth 4 formulas computing iterated matrix multiplication
- The limits of depth reduction for arithmetic formulas
- A super-polynomial lower bound for regular arithmetic formulas
- Affine projections of polynomials
- Approaching the Chasm at Depth Four
This page was built for publication: Depth-4 lower bounds, determinantal complexity: a unified approach
