Quadratic lower bounds for algebraic branching programs and formulas

DOI10.1007/s00037-022-00223-8WikidataQ113906237 ScholiaQ113906237MaRDI QIDQ2159469

Mrinal Kumar, Ben lee Volk, Adrian She, Prerona Chatterjee

Publication date: 1 August 2022

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

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

zbMATH Keywords

lower bounds; algebraic branching programs; algebraic circuit complexity; algebraic formulas

Mathematics Subject Classification ID

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

68Q15: Complexity classes (hierarchies, relations among complexity classes, etc.)

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

Uses Software

• GitHub
• MathOverflow
• lowerbounds-survey