Please note: This seminar will be given online.
Department of Computer Science, Rutgers University
Host: Professor Rafael Oliveira
Arithmetic circuits are a natural model for computing polynomials using basic arithmetic operations like addition and multiplication. The problem of learning arithmetic circuits, a.k.a. reconstruction, is an important and well-studied problem. Here we are given a polynomial (either explicitly as a list of coefficients or using black-box access) and the goal is to find the smallest (or approximately smallest) arithmetic circuit computing it.
In this talk, we will discuss two vastly different paradigms in learning arithmetic circuits, which are worst-case learning and average-case (non-degenerate) learning. We will elaborate on various techniques involved in these paradigms, their similarity, and their differences. Along the way, we will see a worst-case as well as a non-degenerate algorithm for decomposing tensors. Time permitting, we will also discuss some recent progress in non-degenerate learning of “generalized” depth 3 arithmetic circuits.
Bio: Vishwas Bhargava is a final-year Ph.D. student at Rutgers, advised by Shubhangi Saraf. He is broadly interested in the theoretical aspects of computer science; specifically, problems in Computational Complexity theory, Pseudorandomness/derandomization, and problems having Algebraic or Number Theoretic flavor.
To join this seminar on Zoom, please go to https://uwaterloo.zoom.us/j/94328913686?pwd=SWdrMEdXZUJla3pTM1FlcGZIYy9IQT09.
200 University Avenue West
Waterloo, ON N2L 3G1