Seminars

View all Seminars  |  Download ICal for this event

Rank bounds and Polynomial Identity Testing

Series: Bangalore Theory Seminars

Speaker: Akash Sengupta, Rutgers University

Date/Time: Nov 19 11:00:00

Location: CSA Auditorium, (Room No. 104, Ground Floor)

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 will 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.

This talk is based on joint works with Abhibhav Garg and Rafael Oliveira.


Microsoft teams link:

Link


We are grateful to the Kirani family (Link and the Walmart Center for Tech Excellence (Link for generously supporting this seminar series


Hosts: Rameesh Paul, Nirjhar Das, KVN Sreenivas, Rahul Madhavan, Debajyoti Kar