Deterministic identity testing paradigms for bounded top-fanin depth-4 circuits

Speaker

Prateek Dwivedi October 29, 2021.

Abstract

Deterministically solving the Polynomial Identity Testing (PIT) problem is a fundamental computational problem, and it is of pivotal importance in Algebraic Complexity Theory. This intrinsically difficult problem has found its way into many areas of Computer Science. In this talk, we will introduce the problem from the perspective of Algebraic Complexity Theory, discuss its motivations and connections.

Despite decades of effort, there has been little progress on the problem in general. Moreover, under strong restrictions on the circuits, we already have very efficient algorithms. One such well-motivated restriction we consider is depth-4 circuits. Special cases of these circuits are a great source of inspiration for ideas of designing PIT algorithms. However, their inapplicability led us to examine from a different viewpoint. In the talk, we will share these ideas, which helped us in designing efficient algorithms. Further, we will exhibit our newly developed paradigm for designing PIT algorithms.

The results in this talk are a joint work with Pranjal Dutta (CMI & IIT Kanpur) and Nitin Saxena (IIT Kanpur). They appeared in CCC 2021 earlier this year.