Arithmetic Circuit Lower Bounds via Maximum-Rank of Partial Derivative Matrices

DOI10.1145/2898437zbMath1427.68108MaRDI QIDQ4973853

Mrinal Kumar, M. N. Jayalal Sarma, Gaurav Maheshwari

Publication date: 6 December 2019

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

Full work available at URL: https://doi.org/10.1145/2898437

zbMATH Keywords

arithmetic circuits; partial derivative matrix

Mathematics Subject Classification ID

12E05: Polynomials in general fields (irreducibility, etc.)

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

12E30: Field arithmetic

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