Applications of algebraic complexity to unsupervised learning
# 167
Abstract
How hard is it to compute a given multivariate polynomial? In this talk, we will motivate this question and the related problem of showing that certain polynomials are hard to compute. We will sketch some proof techniques for proving hardness and see how these proof techniques lead to efficient algorithms for learning arithmetic circuits and for unsupervised learning.
Neeraj Kayal is currently a Principal Researcher at the Microsoft Research lab in Bengaluru. Dr. Kayal works in the areas of complexity theory, algorithms, and related areas of theoretical computer science. Neeraj Kayal received his B. Tech and Ph.D. from IIT-Kanpur and has held postdoctoral positions at the Institute for Advanced Study, Princeton and at DIMACS (Rutgers University). Together with Manindra Agrawal and Nitin Saxena, he was part of the team that discovered the first deterministic polynomial time algorithm for primality testing. This work received the Godel Prize (2006) and the Fulkerson Prize (2006). His recent work has been focused on algorithms and lower bounds in algebraic complexity theory for which he and his coauthors received some best paper awards at various conferences. For this body of work, he also received the Infosys Prize (2021) and Bhatnagar Award (2022). Most recently, he has been working on unsupervised learning.