Tata Institute of Fundamental Research
On Top Fan-in vs Formal Degree for Depth-3 Arithmetic Circuits
STCS Seminar
Speaker:
Mrinal Kumar (Harvard University
Center for Mathematical
Sciences and Applications
Cambridge
MA 02138, USA)
Organiser:
Ramprasad Saptharishi
Date:
Wednesday, 27 Jun 2018, 14:00 to 15:00
Venue:
A-201 (STCS Seminar Room)
(Scan to add to calendar)
Abstract:
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.
| Speaker: | Mrinal Kumar (Harvard University Center for Mathematical Sciences and Applications Cambridge MA 02138, USA) |
| Organiser: | Ramprasad Saptharishi |
| Date: | Wednesday, 27 Jun 2018, 14:00 to 15:00 |
| Venue: | A-201 (STCS Seminar Room) |
(Scan to add to calendar)
Abstract:
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.
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.