The Limited Power of Powering: Polynomial Identity Testing and a Depth-four Lower Bound for the Permanent

Bruno Grenet, Pascal Koiran, Natacha Portier +1

Polynomial identity testing and arithmetic circuit lower bounds are two central questions in algebraic complexity theory. It is an intriguing fact that these questions are actually…