Computer Science/Discrete Mathematics Seminar I | |

Topic: | Learning arithmetic circuits in the average case via lower bounds |

Speaker: | Ankit Garg |

Affiliation: | Microsoft Research |

Date: | Monday, October 21 |

Time/Room: | 11:00am - 12:00pm/Simonyi Hall 101 |

Video Link: | https://video.ias.edu/csdm/2019/1021-AnkitGarg |

The problem of learning arithmetic circuits is the following: given a polynomial as a black box that is promised to have a small arithmetic circuit computing it, can we find this arithmetic circuit? This problem is hard in the worst case and so previous works have focused on regimes where the NP-hardness doesnâ€™t kick in (e.g. constant top fan-in etc.). We focus on the average case where one assumes certain non-degeneracy assumptions on the circuit (formally these amount to assuming the circuit parameters lie outside a certain variety and hence if they are chosen randomly according to any reasonable distribution, the non-degeneracy condition is satisfied whp). Kayal and Saha gave a meta framework for designing these algorithms for circuit classes where we have lower bounds. They carried this out for depth 3 circuits (sums of products of linear forms) and we (in joint work with Kayal and Saha) carry it out for depth 4 powering circuits (sums of powers of low degree polynomials). I will talk about the meta framework and then about our specific results. I will also talk about a potential application to learning mixtures of general Gaussians.