- This event has passed.
Rank bounds and Polynomial Identity Testing by Prof. Akash
November 17 @ 3:00 pm - 4:00 pm
Venue: Bharti501
Abstract: Polynomial Identity Testing (PIT) is the problem of checking whether a given algebraic circuit computes the zero polynomial. The PIT problem has a myriad of applications, such as algorithms for the perfect matching problem, primality testing, and learning algorithms for sparse polynomials. While there are efficient randomized algorithms for PIT, there is no deterministic poly-time algorithm for general circuits. Derandomizing PIT is a foundational problem in theoretical computer science, as it is also intrinsically related to lower bounds for algebraic circuits and the VP vs. VNP problem.
In this talk, we will discuss the PIT problem for depth-4 circuits. I’ll talk about recent progress on proving rank bounds for depth-4 identities, and the first deterministic poly-time algorithm for depth-4 circuits with top fan-in 3 and constant bottom fan-in. We will discuss algebraic-geometric ideas such as the Stillman uniformity principle, that lead to rank bounds and non-linear generalizations of classical results from combinatorial geometry.
Bio: Prof. Akash is an Assistant Professor in the Department of Computer Science at Rutgers University. I am part of the Theory group at Rutgers. His research interests are in Mathematics and Theoretical Computer Science, in particular algebraic geometry, computational complexity theory, coding theory, combinatorics and number theory.