摘要：We formalize a framework of algebraically natural lower bounds for algebraic
circuits. Just as with the natural proofs notion of Razborov and Rudich (1997) for Boolean
circuit lower bounds, our notion of algebraically natural lower bounds captures nearly all
lower bound techniques known. However, unlike in the Boolean setting, there has been
no concrete evidence demonstrating that this is a barrier to obtaining super-polynomial
lower bounds for general algebraic circuits, as there is little understanding whether algebraic
circuits are expressive enough to support “cryptography” secure against algebraic circuits.
