Arithmetic Circuit Lower Bounds via MaxRank

Mrinal Kumar, Gaurav Maheshwari, Jayalal Sarma M. N

We introduce the polynomial coefficient matrix and identify maximum rank of this matrix under variable substitution as a complexity measure for multivariate polynomials. We use our…