Abstract
For a class of polynomials C, an equation for C is a nonzero polynomial that vanishes on the coefficient vectors of all polynomials from C. Typically, an equation for C depends on many more variables than the polynomials in C. For instance, if C contains n-variate multilinear polynomials, then an equation for C depends on 2^n variables.
An equation P for a class C can be seen as a property (or a 'weakness') of C. Thus the circuit complexity of P itself is interesting in the context of proving lower bounds, when C is a well-defined class, like VP: poly-sized algebraic circuits. For example, several known lower bounds against algebraic circuit classes yield 'efficiently computable' equations against those classes.
A natural question therefore is whether VP has equations that are efficiently computable, i.e. equations in VP. Such an equation would be a 'VP-natural proof for VP': a VP-computable equation for the class VP. This is the framework of algebraically natural proofs, introduced by Forbes, Shpilka and Volk (2018) and Grochow, Kumar, Saks and Saraf (2017). In the same work, Forbes et al. also rule out 'D-natural proofs for VP' for some structured subclasses D of VP. In joint works with Chatterjee, Kumar, Saptharishi and Ramya, we answer questions about VP-natural proofs for C, for some interesting classes C. The talk is aimed at understanding these results in the context of VP-natural proofs for VP and more generally in the context of proving lower bounds against algebraic circuits.