Towards an algebraic natural proofs barrier via polynomial identity testing

Joshua A. Grochow, Mrinal Kumar, Michael Saks +1

We observe that a certain kind of algebraic proof - which covers essentially all known algebraic circuit lower bounds to date - cannot be used to prove lower bounds against VP if a…