Description:

Wednesday / CS Seminar
January 22nd / 12:00 PM
Hybrid / Mudd 3514

Speaker
Ankit Garg, Microsoft Research India

Talk Title
Arithmetic circuits: lower bounds, learning and applications

Abstract
Arithmetic circuits are a natural model for computing polynomials via the basic operations of addition and multiplication. One of the fundamental open problems in this area is of proving lower bounds, i.e. finding an explicit polynomial that cannot be computed by polynomial sized arithmetic circuits (aka the VP vs VNP problem). While the question of proving lower bounds for general arithmetic circuits is still open, there has been remarkable progress in proving lower bounds for restricted classes of arithmetic circuits. Another important problem in this area is that of learning arithmetic circuits: given a polynomial (via query or black box access), output a small arithmetic circuit computing it (if one exists). This problem is hard in the worst case. I will present a meta framework for learning arithmetic circuits in the non-degenerate case using lower bound methods. We instantiate and implement this meta framework for various classes of arithmetic circuits. Then I will talk about extending the algorithms to the noisy setting as well as surprising and remarkable applications to classical problems in machine learning such as subspace clustering and mixtures of Gaussians. This is based on joint works with Pritam Chandra, Neeraj Kayal, Kunal Mittal, Chandan Saha and Tanmay Sinha.

Biography
Ankit Garg is a Senior Researcher at Microsoft Research India since July 2018. Prior to this, he was a Postdoctoral Researcher at Microsoft Research New England from 2016 - 2018. He completed his PhD in 2016 from Princeton University under the supervision of Prof Mark Braverman. His research has spanned several areas of theoretical computer science such as communication complexity, arithmetic complexity, optimization, mixture models and optimization. Several of his research papers have been published in top conferences in computer science such as STOC, FOCS, CCC, NeuRIPS and QIP, and recognized by Simons award for graduate students in theoretical computer science and a Siebel scholarship.

Research/Interest Areas
Theoretical Computer Science, Algorithms, Computational Complexity Theory

---
Zoom: https://northwestern.zoom.us/j/92525649422?pwd=N6DlLBx6RRAtrar8vk27te6cjmzqXP.1
Panopto: https://northwestern.hosted.panopto.com/Panopto/Pages/Viewer.aspx?id=4d9fd60c-89e5-48f6-bbdb-b261015638de
DEI Minute: tinyurl.com/cspac-dei-minute