Computer Science/Discrete Mathematics Seminar II

I will describe the very recent breakthrough result by Gupta, Kamath, Kayal and Saptharishi which shows that every polynomial P in n variables, of degree d which is polynomial in n, and which can be computed by a polynomial sized arithmetic circuit over the complex numbers, can be also computed by a *depth 3* arithmetic circuit of size sub exponential in d; specifically size 2^{sqrt d polylog n} (the actual paper gives a more precise bound depending on the degree of the polynomial and size of the arithmetic circuit). In particular there exists a depth 3 arithmetic circuit computing the d by d determinant of size 2^{sqrt d log d}. Such results were previously shown for reduction to depth 4 arithmetic circuits, and it is totally remarkable (and prior to this totally unsuspected) that it is also true for reduction to depth 3 circuits.