On Top Fan-in vs Formal Degree for Depth-3 Arithmetic Circuits

A well known fact is that there are polynomials of degree 2 (for instance, inner product, or elementary symmetric polynomials of degree 2), such that any representation of these as a sum of product of affine forms requires Omega(n) summands, where n is the total number of variables.

In this talk, we will see that over the field of complex numbers, we can approximate these polynomials to arbitrary accuracy (in the border complexity sense) by a sum of 3 summands, each of which is a product of affine forms. Or, more generally, *every* homogeneous polynomial of degree d can be approximated by a sum of d+1 terms, each term being a product of affine forms.

I hope to show the complete proof, which is an elementary, simple, short and self-contained argument and requires no prior exposure to the notion of border computation.