Computer Science/Discrete Mathematics Seminar II | |

Topic: | The Chasm at Depth 3 |

Speaker: | Shubhangi Saraf |

Affiliation: | Rutgers, The State University of New Jersey |

Date: | Tuesday, February 19 |

Time/Room: | 10:30am - 12:30pm/S-101 |

Video Link: | https://video.ias.edu/csdm/1213/0219-ShubhangiSaraf |

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.