On the Power of Border of Depth-3 Arithmetic Circuits

DOI10.1145/3371506zbMath1499.68106arXiv1804.03303MaRDI QIDQ5053057

Mrinal Kumar

Publication date: 5 December 2022

Published in: ACM Transactions on Computation Theory (Search for Journal in Brave)

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

zbMATH Keywords

lower bounds; algebraic complexity; border complexity; depth reductions

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