A quadratic lower bound for homogeneous algebraic branching programs

DOI10.1007/s00037-019-00186-3zbMath1429.68072MaRDI QIDQ2323359

Mrinal Kumar

Publication date: 30 August 2019

Published in: Computational Complexity (Search for Journal in Brave)

Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2017/7513/

zbMATH Keywords

lower bounds; algebraic complexity; algebraic branching programs; arithmetic circuits; determinantal complexity

Mathematics Subject Classification ID

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

68Q06: Networks and circuits as models of computation; circuit complexity

Uses Software

• GitHub
• lowerbounds-survey